An Exact Algorithm for the Uniformly-Oriented Steiner Tree Problem

Nielsen B. K., Winther P., Martin Tvede Zachariasen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

24 Citations (Scopus)

Abstract

An exact algorithm to solve the Steiner tree problem for uniform orientation metrics in the plane is presented. The algorithm is based on the two-phase model, consisting of full Steiner tree (FST) generation and concatenation, which has proven to be very successfulf or the rectilinear and Euclidean Steiner tree problems. By applying a powerful canonicalf orm for the FSTs, the set of optimal solutions is reduced considerably. Computational results both for randomly generated problem instances and VLSI design instances are provided. The new algorithm solves most problem instances with 100 terminals in seconds, and problem instances with up to 10000 terminals have been solved to optimality.
Original languageEnglish
Title of host publicationAlgorithms ESA 2002
Subtitle of host publication10th annual European symposium
EditorsRolf Möhring, Rajeev Raman
Place of PublicationGermany
PublisherSpringer Berlin Heidelberg
Pages760-772
Number of pages12
Edition1
ISBN (Electronic)978-3-540-45749-7
ISBN (Print)978-3-540-44180-9
DOIs
Publication statusPublished - 2002
EventEuropean Symposium on Algorithms - Rome, Italy
Duration: 17 Sep 200221 Sep 2002
Conference number: 10

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume2461

Conference

ConferenceEuropean Symposium on Algorithms
Country/TerritoryItaly
CityRome
Period17/09/0221/09/02

Keywords

  • minimum span tree
  • exact a
  • steiner point
  • steiner tree problem
  • steiner minimum tree

Fingerprint

Dive into the research topics of 'An Exact Algorithm for the Uniformly-Oriented Steiner Tree Problem'. Together they form a unique fingerprint.

Cite this