Parallel Heuristics for the Steiner Tree Problem in Images without Sorting or Routing
Title | Parallel Heuristics for the Steiner Tree Problem in Images without Sorting or Routing |
Publication Type | Technical Report |
Year of Publication | 1989 |
Authors | Hambrusch, S. E., & TeWinkel L. |
Other Numbers | 547 |
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. |
URL | http://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 |