Show simple item record

dc.contributor.authorArrighi, Emmanuel
dc.contributor.authorDe Oliveira Oliveira, Mateus
dc.description.abstractIn 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.en_US
dc.publisherSchloss Dagstuhl, Leibniz-Zentrum für Informatiken_US
dc.rightsNavngivelse 4.0 Internasjonal*
dc.titleThree Is Enough for Steiner Treesen_US
dc.typeJournal articleen_US
dc.typePeer revieweden_US
dc.rights.holderCopyright Emmanuel Arrighi and Mateus de Oliveira Oliveiraen_US
dc.source.journalLeibniz International Proceedings in Informaticsen_US
dc.relation.projectNotur/NorStore: NN9535Ken_US
dc.relation.projectNorges forskningsråd: 288761en_US
dc.relation.projectNorges forskningsråd: 274526en_US
dc.identifier.citationLeibniz International Proceedings in Informatics. 2021, 190, 5:1-5:15.en_US

Files in this item


This item appears in the following Collection(s)

Show simple item record

Navngivelse 4.0 Internasjonal
Except where otherwise noted, this item's license is described as Navngivelse 4.0 Internasjonal