TY - JOUR
T1 - Rectilinear Full Steiner Tree Generation
AU - Zachariasen, Martin
PY - 1999
Y1 - 1999
N2 - The fastest exact algorithm (in practice) for the rectilinear Steiner tree problem in the plane uses a two-phase scheme: First, a small but sufficient set of full Steiner trees (FSTs) is generated and then a Steiner minimum tree is constructed from this set by using simple backtrack search, dynamic programming, or an integer programming formulation. FST generation methods can be seen as problem-reduction algorithms and are also useful as a first step in providing good upper and lower bounds for large instances. Currently, the time needed to generate FSTs poses a significant overhead for FST-based exact algorithms. In this paper, we present a very efficient algorithm for the rectilinear FST generation problem which removes this overhead completely. Based on information obtained in a preprocessing phase, the new algorithm grows FSTs while applying several new and important optimality conditions. For randomly generated instances, approximately 4n FSTs are generated (where n is the number of terminals). The observed running time is quadratic and the FSTs for a 10,000 terminal instance can, on average, be generated within 5 minutes.
AB - The fastest exact algorithm (in practice) for the rectilinear Steiner tree problem in the plane uses a two-phase scheme: First, a small but sufficient set of full Steiner trees (FSTs) is generated and then a Steiner minimum tree is constructed from this set by using simple backtrack search, dynamic programming, or an integer programming formulation. FST generation methods can be seen as problem-reduction algorithms and are also useful as a first step in providing good upper and lower bounds for large instances. Currently, the time needed to generate FSTs poses a significant overhead for FST-based exact algorithms. In this paper, we present a very efficient algorithm for the rectilinear FST generation problem which removes this overhead completely. Based on information obtained in a preprocessing phase, the new algorithm grows FSTs while applying several new and important optimality conditions. For randomly generated instances, approximately 4n FSTs are generated (where n is the number of terminals). The observed running time is quadratic and the FSTs for a 10,000 terminal instance can, on average, be generated within 5 minutes.
M3 - Journal article
VL - 33
SP - 125
EP - 143
JO - NETWORKS
JF - NETWORKS
IS - 2
ER -