Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View

DOI10.4230/lipics.ipec.2020.16arXiv2002.03583OpenAlexW3005276533MaRDI QIDQ6068262

Dušan Knop, Radek Hušek, Tomáš Masařík

Publication date: 13 November 2023

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

zbMATH Keywords

approximationminimum spanning treeSteiner treestar contractions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (1)

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices

Cites Work

• A note on two problems in connexion with graphs
• A practical greedy approximation for the directed Steiner tree problem
• A fast algorithm for Steiner trees
• Maintaining bridge-connected and biconnected components on-line
• The Steiner tree problem
• Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm
• SCIP-Jack -- a solver for STP and variants with parallelization extensions
• An 11/6-approximation algorithm for the network Steiner problem
• Dynamic programming for minimum Steiner trees
• Contraction-Based Steiner Tree Approximations in Practice
• Thek-Steiner Ratio in Graphs
• Solving Steiner tree problems in graphs to optimality
• Strong Steiner Tree Approximations in Practice
• Preprocessing Steiner problems from VLSI layout
• Reducibility among Combinatorial Problems
• Steiner Tree Approximation via Iterative Randomized Rounding
• The steiner problem in graphs
• A faster approximation algorithm for the Steiner problem in graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View