Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
From MaRDI portal
Publication:6058195
DOI10.4230/lipics.approx/random.2020.63arXiv1911.09150OpenAlexW3082434130MaRDI QIDQ6058195
Yu-Hao Zhang, Bundit Laekhanukit, Hao-Ting Wei, Chun-Hsiang Chan
Publication date: 31 October 2023
Full work available at URL: https://arxiv.org/abs/1911.09150
Related Items (2)
On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Multi-rooted greedy approximation of directed Steiner trees with applications
- Approximating minimum-cost edge-covers of crossing biset-families
- An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
- A partition-based relaxation for Steiner trees
- New geometry-inspired relaxations and algorithms for the metric Steiner tree problem
- A series of approximation algorithms for the acyclic directed Steiner tree problem
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Approximating minimum power covers of intersecting families and directed edge-connectivity problems
- On Rajagopalan and Vazirani's \(\frac{3}{2}e\)-approximation bound for the iterated 1-Steiner heuristic
- Directed vertex-connectivity augmentation
- Increasing the rooted connectivity of a digraph by one
- Rounding algorithms for covering problems
- A primal-dual approximation algorithm for generalized Steiner network problems
- Approximating subset \(k\)-connectivity problems
- Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- Design networks with bounded pairwise distance
- Approximation Algorithms for Minimum-Cost $k\hbox{-}(S,T)$ Connected Digraphs
- Approximating minimum-cost connectivity problems via uncrossable bifamilies
- A threshold of ln n for approximating set cover
- A Graph Reduction Step Preserving Element-Connectivity and Applications
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
- Erratum
- Approximating Directed Steiner Problems via Tree Embedding
- Hardness of Approximation for Vertex-Connectivity Network Design Problems
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- An $O(\log^2{k})$-Approximation Algorithm for the $k$-Vertex Connected Spanning Subgraph Problem
- Approximation Algorithms for Directed Steiner Problems
- Approximating Rooted Steiner Networks
- Dominator Tree Certification and Divergent Spanning Trees
- Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree
- O (log 2 k / log log k )-approximation algorithm for directed Steiner tree
- Efficient probabilistically checkable proofs and applications to approximations
- Analytical approach to parallel repetition
- On Survivable Set Connectivity
- A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs
- Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems
- Steiner Tree Approximation via Iterative Randomized Rounding
- Matroids and integrality gaps for hypergraphic steiner tree relaxations
- Linear Programming Hierarchies Suffice for Directed Steiner Tree
- Approximating k-node Connected Subgraphs via Critical Graphs
This page was built for publication: Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
