Reorganizing topologies of Steiner trees to accelerate their eliminations

DOI10.1142/S1793830920500032zbMATH Open1440.90082arXiv1511.03407OpenAlexW2980902051WikidataQ127031727 ScholiaQ127031727MaRDI QIDQ5216441FDOQ5216441

Authors: Aymeric Grodet, Takuya Tsuchiya 

Publication date: 18 February 2020

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Abstract: We describe a technique to reorganize topologies of Steiner trees by exchanging neighbors of adjacent Steiner points. We explain how to use the systematic way of building trees, and therefore topologies, to find the correct topology after nodes have been exchanged. Topology reorganizations can be inserted into the enumeration scheme commonly used by exact algorithms for the Euclidean Steiner tree problem in $d$-space, providing a method of improvement different than the usual approaches. As an example, we show how topology reorganizations can be used to dynamically change the exploration of the usual branch-and-bound tree when two Steiner points collide during the optimization process. We also turn our attention to the erroneous use of a pre-optimization lower bound in the original algorithm and give an example to confirm its usage is incorrect. In order to provide numerical results on correct solutions, we use planar equilateral points to quickly compute this lower bound, even in dimensions higher than two. Finally, we describe planar twin trees, identical trees yielded by different topologies, whose generalization to higher dimensions could open a new way of building Steiner trees.

Full work available at URL: https://arxiv.org/abs/1511.03407

Recommendations

• An Improved Algorithm for Steiner Trees
• An improved algorithm for computing Steiner minimal trees in Euclidean \(d\)-space
• Geometric conditions for Euclidean Steiner trees in \(\mathbb R^d\)
• An algorithm for the steiner problem in the euclidean plane
• Euclidean Steiner minimum trees: An improved exact algorithm

zbMATH Keywords

optimizationSteiner treesbranch-and-boundEuclidean Steiner tree problem\(d\)-space

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Trees (05C05)

Cites Work

• The Steiner tree problem
• Steiner Minimal Trees
• The Complexity of Computing Steiner Minimal Trees
• How to find Steiner minimal trees in Euclidean \(d\)-space
• Geometric conditions for Euclidean Steiner trees in \(\mathbb R^d\)
• An improved algorithm for computing Steiner minimal trees in Euclidean \(d\)-space
• Approximations and lower bounds for the length of minimal Euclidean Steiner trees
• An overview of exact algorithms for the Euclidean Steiner tree problem in \(n\)-space
• A Dynamic Adaptive Relaxation Scheme Applied to the Euclidean Steiner Minimal Tree Problem

Uses Software

• DIMACS

This page was built for publication: Reorganizing topologies of Steiner trees to accelerate their eliminations

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