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 |