scientific article; zbMATH DE number 7053371
From MaRDI portal
Publication:5743494
zbMath1421.68202MaRDI QIDQ5743494
Guyslain Naves, Bundit Laekhanukit, Adrian Vetta, Joseph Cheriyan
Publication date: 10 May 2019
Full work available at URL: https://dl.acm.org/citation.cfm?id=2095235
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Connectivity (05C40)
Related Items (2)
Approximating subset \(k\)-connectivity problems ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
Cites Work
- Unnamed Item
- Unnamed Item
- A factor 2 approximation algorithm for the generalized Steiner network problem
- A note on Rooted Survivable Networks
- Inapproximability of survivable networks
- Design networks with bounded pairwise distance
- The Design of Approximation Algorithms
- An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity
- Proof verification and the hardness of approximation problems
- A threshold of ln n for approximating set cover
- The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
- Polylogarithmic inapproximability
- Probabilistic checking of proofs
- A Parallel Repetition Theorem
- Hardness of Approximation for Vertex-Connectivity Network Design Problems
- Approximation Algorithms for Directed Steiner Problems
- Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
- Applications of approximation algorithms to cooperative games
- A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
- Parameterized Complexity of Arc-Weighted Directed Steiner Problems
This page was built for publication:
