Rectilinear Full Steiner Tree Generation

Martin Zachariasen

Research output: Journal Article or Conference Article in JournalJournal articleResearchpeer-review

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 languageEnglish
JournalNetworks
Volume33
Issue number2
Pages (from-to)125-143
ISSN0028-3045
Publication statusPublished - 1999
Externally publishedYes

Keywords

  • Rectilinear Steiner tree
  • Exact algorithms
  • Full Steiner tree generation
  • Dynamic programming
  • Integer programming

Fingerprint

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

Cite this