Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2021.5
URN: urn:nbn:de:0030-drops-137775
URL: https://drops.dagstuhl.de/opus/volltexte/2021/13777/
Arrighi, Emmanuel ; de Oliveira Oliveira, Mateus
Three Is Enough for Steiner Trees
| pdf-format: |
|
Abstract
In the Steiner tree problem, the input consists of an edge-weighted graph G together with a set S of terminal vertices. The goal is to find a minimum weight tree in G that spans all terminals. This fundamental NP-hard problem has direct applications in many subfields of combinatorial optimization, such as planning, scheduling, etc. In this work we introduce a new heuristic for the Steiner tree problem, based on a simple routine for improving the cost of sub-optimal Steiner trees: first, the sub-optimal tree is split into three connected components, and then these components are reconnected by using an algorithm that computes an optimal Steiner tree with 3-terminals (the roots of the three components). We have implemented our heuristic into a solver and compared it with several state-of-the-art solvers on well-known data sets. Our solver performs very well across all the data sets, and outperforms most of the other benchmarked solvers on very large graphs, which have been either obtained from real-world applications or from randomly generated data sets.
BibTeX - Entry
@InProceedings{arrighi_et_al:LIPIcs.SEA.2021.5,
author = {Arrighi, Emmanuel and de Oliveira Oliveira, Mateus},
title = {{Three Is Enough for Steiner Trees}},
booktitle = {19th International Symposium on Experimental Algorithms (SEA 2021)},
pages = {5:1--5:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-185-6},
ISSN = {1868-8969},
year = {2021},
volume = {190},
editor = {Coudert, David and Natale, Emanuele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13777},
URN = {urn:nbn:de:0030-drops-137775},
doi = {10.4230/LIPIcs.SEA.2021.5},
annote = {Keywords: Steiner Tree, Heuristics, 3TST}
}
| Keywords: | Steiner Tree, Heuristics, 3TST | |
| Seminar: | 19th International Symposium on Experimental Algorithms (SEA 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 31.05.2021 | |
| Supplementary Material: | Software: https://github.com/AutoProving/3TST archived at: https://archive.softwareheritage.org/swh:1:dir:740b703cb9dceee55ef1571f49d1b58701a2082f |
