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

DOI10.1007/S12532-018-0135-8zbMATH Open1411.90225OpenAlexW2603633927MaRDI QIDQ1741111FDOQ1741111

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

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

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)

Cites Work

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

Cited In (16)

• Computing Euclidean Steiner trees over segments
• An efficient solver for large-scale onshore wind farm siting including cable routing
• Enabling research through the SCIP Optimization Suite 8.0
• 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
• 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
• Structural properties of minimum multi-source multi-sink Steiner networks in the Euclidean plane
• A robust and scalable algorithm for the Steiner problem in graphs
• GeoSteiner
• Solving Steiner trees: Recent advances, challenges, and perspectives
• Title not available (Why is that?)
• Approximate Euclidean Steiner trees
• Tropical geometric variation of tree shapes
• Approximation algorithms for Steiner forest: An experimental study

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)