Abstract
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 language | English |
---|---|
Journal | Networks |
Volume | 33 |
Issue number | 2 |
Pages (from-to) | 125-143 |
ISSN | 0028-3045 |
Publication status | Published - 1999 |
Externally published | Yes |
Keywords
- Rectilinear Steiner tree
- Exact algorithms
- Full Steiner tree generation
- Dynamic programming
- Integer programming