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

DOI10.1137/18M1209489zbMath1462.68138MaRDI QIDQ5857009

Andreas Emil Feldmann, Pavel Veselý, Tomáš Toufar, Tomáš Masařík, Pavel Dvořák, Dušan Knop

Publication date: 30 March 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmsSteiner treeparameterized algorithmsSteiner forest

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (3)

On the complexity of the cable-trench problem ⋮ \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms ⋮ Lossy kernelization of same-size clustering

Uses Software

• GitHub

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• The Steiner tree problem
• An 11/6-approximation algorithm for the network Steiner problem
• Extending the kernel for planar Steiner tree to the number of Steiner vertices
• Dynamic programming for minimum Steiner trees
• Fixed-Parameter and Approximation Algorithms: A New Look
• The Design of Approximation Algorithms
• Fourier meets M\"{o}bius: fast subset convolution
• Polylogarithmic inapproximability
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
• Thek-Steiner Ratio in Graphs
• Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Approximation Algorithms for Directed Steiner Problems
• Kernelization Lower Bounds Through Colors and IDs
• Lossy kernelization
• Reducibility among Combinatorial Problems
• Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
• On the Parameterized Complexity of Approximating Dominating Set
• Analytical approach to parallel repetition
• Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
• Steiner Tree Approximation via Iterative Randomized Rounding
• Parameterized Algorithms
• The steiner problem in graphs
• Parameterized Complexity of Arc-Weighted Directed Steiner Problems
• Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View

This page was built for publication: Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices