scientific article

DOI10.4230/LIPICS.STACS.2018.26zbMath1487.68175arXiv1710.00668MaRDI QIDQ3304124

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

Publication date: 5 August 2020

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

approximation algorithmsSteiner treeparameterized algorithmsSteiner forestlossy kernelization

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 (6)

Unnamed Item ⋮ Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems ⋮ Lossy kernelization of same-size clustering ⋮ On the Parameterized Approximability of Contraction to Classes of Chordal Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• The Steiner tree problem
• On subexponential and FPT-time inapproximability
• Extending the kernel for planar Steiner tree to the number of Steiner vertices
• Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
• Fixed-Parameter and Approximation Algorithms: A New Look
• An O ( n log n ) approximation scheme for Steiner tree in planar graphs
• The Design of Approximation Algorithms
• Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
• Fourier meets M\"{o}bius: fast subset convolution
• Polylogarithmic inapproximability
• Lossy Kernels for Graph Contraction Problems
• 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
• A (1+epsilon)-Approximation for Unsplittable Flow on a Path in Fixed-Parameter Running Time
• Parameterized Approximation Schemes Using Graph Widths
• Analytical approach to parallel repetition
• Steiner Tree Approximation via Iterative Randomized Rounding
• Parameterized Algorithms
• The steiner problem in graphs

This page was built for publication: