The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study

DOI10.1007/s12532-018-0135-8zbMath1411.90225OpenAlexW2603633927MaRDI QIDQ1741111

Pawel Winter, David M. Warme, Martin Zachariasen, Daniel Dahl Juhl

Publication date: 3 May 2019

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: http://dimacs11.zib.de/workshop/JuhlWarmeWinterZachariasen.pdf

zbMATH Keywords

exact algorithmcomputational studyrectilinear Steiner tree problemeuclidean Steiner tree problemfixed orientation Steiner tree problem

Mathematics Subject Classification ID

Trees (05C05) Integer programming (90C10) Hypergraphs (05C65) Combinatorial optimization (90C27) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35) Euclidean analytic geometry (51N20)

Related Items (12)

New pruning rules for the Steiner tree problem and 2-connected Steiner network problem ⋮ A robust and scalable algorithm for the Steiner problem in graphs ⋮ Approximate Euclidean Steiner trees ⋮ Tropical geometric variation of tree shapes ⋮ Approximation algorithms for Steiner forest: An experimental study ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Structural properties of minimum multi-source multi-sink Steiner networks in the Euclidean plane ⋮ Unnamed Item ⋮ Computing Euclidean Steiner trees over segments ⋮ Implications, conflicts, and reductions for Steiner trees ⋮ Implications, conflicts, and reductions for Steiner trees ⋮ GeoSteiner

Uses Software

• LEDA
• CPLEX
• OR-Library
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving rectilinear Steiner tree problems exactly in theory and practice
• Steiner trees for fixed orientation metrics
• The Steiner tree problem
• Rectilinear group Steiner trees and applications in VLSI design
• On Steiner trees and minimum spanning trees in hypergraphs
• Concatenation-based greedy heuristics for the Euclidean Steiner tree problem
• Optimal interconnection trees in the plane. Theory, algorithms and applications
• Canonical forms and algorithms for Steiner trees in uniform orientation metrics
• THE UNIFORM ORIENTATION STEINER TREE PROBLEM IS NP-HARD
• On Some Distance Problems in Fixed Orientations
• An algorithm for the steiner problem in the euclidean plane
• An O(n logn) heuristic for steiner minimal tree problems on the euclidean metric
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Complexity of Computing Steiner Minimal Trees
• Euclidean Steiner minimum trees: An improved exact algorithm
• Thirty‐five‐point rectilinear steiner minimal trees in a day
• On Steiner’s Problem with Rectilinear Distance
• Steiner Minimal Trees
• Steiner tree problems

This page was built for publication: The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study