Parallel Heuristics for the Steiner Tree Problem in Images without Sorting or Routing

TitleParallel Heuristics for the Steiner Tree Problem in Images without Sorting or Routing
Publication TypeTechnical Report
Year of Publication1989
AuthorsHambrusch, S. E., & TeWinkel L.
Other Numbers547
Abstract

In this paper we consider the problem of determining a minimum-cost rectilinear Steiner tree when the input is an n X n binary array I which is stored in an n X n mesh of processors. We present several heuristic mesh algorithms for this NP-hard problem. A major design criteria of our algorithms is to avoid sorting and routing which are expensive operations in practice. All of our algorithms have a O(n log k) running time, where k is the number of connected components formed by the entries of value `1'. The main contribution of the paper are two conceptually different methods for connecting components in an image.

URLhttp://www.icsi.berkeley.edu/pubs/techreports/tr-89-048.pdf
Bibliographic Notes

ICSI Technical Report TR-89-048

Abbreviated Authors

S. Hambrusch and L. TeWinkel

ICSI Publication Type

Technical Report