Exact Algorithms for Plane Steiner Tree Problems: A Computational Study

D. M. Warme, P. Winter, M. Zachariasen

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

Abstract

We present a computational study of exact algorithms for the Euclidean and rectilinear Steiner tree problems in the plane. These algorithms --- which are based on the generation and concatenation of full Steiner trees --- are much more efficient than other approaches and allow exact solutions of problem instances with more than 2000 terminals. The full Steiner tree generation algorithms for the two problem variants share many algorithmic ideas and the concatenation part is identical (integer programming formulation solved by branch-and-cut). Performance statistics for randomly generated instances, public library instances and ``difficult'' instances with special structure are presented. Also, results on the comparative performance on the two problem variants are given.
Original languageEnglish
Title of host publicationAdvances in Steiner Trees
EditorsDing-Zhu Du, J. M. Smith, J. H. Rubinstein
Place of PublicationBoston, MA
PublisherSpringer US
Pages81-116
Number of pages36
ISBN (Print)978-1-4757-3171-2
DOIs
Publication statusPublished - 2000

Keywords

  • steiner tree problem
  • Algorithms

Fingerprint

Dive into the research topics of 'Exact Algorithms for Plane Steiner Tree Problems: A Computational Study'. Together they form a unique fingerprint.

Cite this