Rectilinear Full Steiner Tree Generation

Research output: Contribution to journalArticlepeer-review

35 Citations (Scopus)


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. 
Original languageEnglish
Pages (from-to)125-143
Number of pages19
Issue number2
Publication statusPublished - 1999


Dive into the research topics of 'Rectilinear Full Steiner Tree Generation'. Together they form a unique fingerprint.

Cite this