License: Creative Commons Attribution 4.0 International 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
Go to the corresponding LIPIcs Volume Portal

Arrighi, Emmanuel ; de Oliveira Oliveira, Mateus

Three Is Enough for Steiner Trees

LIPIcs-SEA-2021-5.pdf (0.8 MB)


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

  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 =		{},
  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
Collection: 19th International Symposium on Experimental Algorithms (SEA 2021)
Issue Date: 2021
Date of publication: 31.05.2021
Supplementary Material: Software: archived at:

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI