Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems
From MaRDI portal
Publication:5384080
DOI10.1137/1.9781611973402.118zbMath1422.68084arXiv1212.0752OpenAlexW1582339485MaRDI QIDQ5384080
Publication date: 20 June 2019
Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1212.0752
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)
Related Items (12)
$O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm ⋮ Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ Unnamed Item ⋮ A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems ⋮ Tree-like distance colouring for planar graphs of sufficient girth ⋮ An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ Approximating source location and star survivable network problems ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems ⋮ Parameterized inapproximability of independent set in \(H\)-free graphs ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
This page was built for publication: Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems
