Solving Steiner trees: Recent advances, challenges, and perspectives. Issue 2 (27th November 2020)

• Record Type: Journal Article
• Authors: Ljubić, Ivana
• Is Part Of: Networks. Volume 77:Issue 2(2021)
• Page Start: 177
• Page End: 204
• Publication Date: 2020-11-27
• Subjects: combinatorial optimization -- exact methods -- heuristics -- integer programming -- Steiner tree problem; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.22005
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: The Steiner tree problem (STP) in graphs is one of the most studied problems in combinatorial optimization. Since its inception in 1970, numerous articles published in the journal Networks have stimulated new theoretical and computational studies on Steiner trees: from approximation algorithms, heuristics, metaheuristics, all the way to exact algorithms based on (mixed) integer linear programming, fixed parameter tractability, or combinatorial branch‐and‐bounds. The pervasive applicability and relevance of Steiner trees have been reinforced by the recent 11th DIMACS Implementation Challenge in 2014 and the PACE 2018 Challenge. This article provides an overview of the rich developments from the last three decades for the STP in graphs and highlights the most recent computational studies for some of its closely related variants.