Publication Details
Title: Parallel Heuristics for the Steiner Tree Problem in Images without Sorting or Routing
Author: S. Hambrusch and L. TeWinkel
Group: ICSI Technical Reports
Date: August 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-048.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-89-048
Bibliographic Reference:
S. Hambrusch and L. TeWinkel. Parallel Heuristics for the Steiner Tree Problem in Images without Sorting or Routing. ICSI Technical Report TR-89-048, August 1989
Author: S. Hambrusch and L. TeWinkel
Group: ICSI Technical Reports
Date: August 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-048.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-89-048
Bibliographic Reference:
S. Hambrusch and L. TeWinkel. Parallel Heuristics for the Steiner Tree Problem in Images without Sorting or Routing. ICSI Technical Report TR-89-048, August 1989