scientific article; zbMATH DE number 7378620

DOI10.4230/LIPIcs.APPROX-RANDOM.2018.8MaRDI QIDQ5009500

Guy Even, Daniel Vaz, Syamantak Das, Bundit Laekhanukit, Parinya Chalermsook

Publication date: 4 August 2021

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

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

zbMATH Keywords

approximation algorithmshardness of approximationgroup Steiner treesurvivable network design

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
• Approximating fault-tolerant group-Steiner problems
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A primal-dual approximation algorithm for generalized Steiner network problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Linear Programming and Sequential Decisions
• Approximating minimum-cost connectivity problems via uncrossable bifamilies
• Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
• Polyhedral Characterization of Discrete Dynamic Programming
• Approximation Algorithms for Network Design with Metric Costs
• Polylogarithmic inapproximability
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs
• On Survivable Set Connectivity
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Sparsest cut on bounded treewidth graphs

This page was built for publication: