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

DOI10.1007/S12532-018-0135-8MaRDI QIDQ1741111zbMATH OpenOpenAlexFDO

Authors David M. Warme, Pawel Winter, 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) Combinatorial optimization (90C27) Integer programming (90C10) Hypergraphs (05C65) Euclidean analytic geometry (51N20) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)

Recommendations

• Euclidean Steiner minimum trees: An improved exact algorithm
• Publication:4945796
• Improved computation of plane Steiner minimal trees
• scientific article; zbMATH DE number 1305548
• An algorithm for the steiner problem in the euclidean plane

Cites work

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

Cited in

(16)

• An efficient solver for large-scale onshore wind farm siting including cable routing
• An initial study of budgeted Steiner networks
• New pruning rules for the Steiner tree problem and 2-connected Steiner network problem
• Implications, conflicts, and reductions for Steiner trees
• Implications, conflicts, and reductions for Steiner trees
• Structural properties of minimum multi-source multi-sink Steiner networks in the Euclidean plane
• Approximation algorithms for solving the 1-line minimum Steiner tree of line segments problem
• Faster algorithms for Steiner tree and related problems: from theory to practice
• GeoSteiner
• Computing Euclidean Steiner trees over segments
• Approximate Euclidean Steiner trees
• A robust and scalable algorithm for the Steiner problem in graphs
• Enabling research through the SCIP Optimization Suite 8.0
• Tropical geometric variation of tree shapes
• Solving Steiner trees: Recent advances, challenges, and perspectives
• Approximation algorithms for Steiner forest: An experimental study

Describes a project that uses

Uses Software

• LEDA
• CPLEX
• OR-Library
• DIMACS

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1741111)