On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
From MaRDI portal
Publication:2117101
DOI10.1007/978-3-030-79416-3_20OpenAlexW3174748938MaRDI QIDQ2117101
Publication date: 21 March 2022
Full work available at URL: https://arxiv.org/abs/2009.10160
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Multi-rooted greedy approximation of directed Steiner trees with applications
- A series of approximation algorithms for the acyclic directed Steiner tree problem
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Tight approximation algorithm for connectivity augmentation problems
- Inapproximability of survivable networks
- Rooted \(k\)-connections in digraphs
- Approximating the weight of shallow Steiner trees
- Improved approximation algorithms for minimum cost node-connectivity augmentation problems
- An improved approximation scheme for the Group Steiner Problem
- Approximating Source Location and Star Survivable Network Problems
- Prize-Collecting Survivable Network Design in Node-Weighted Graphs
- Polylogarithmic inapproximability
- Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
- 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
- Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree
- Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems
- Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
- O (log 2 k / log log k )-approximation algorithm for directed Steiner tree
- Spider covers for prize-collecting network activation problem
- 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
- Approximating Steiner Networks with Node Weights
- Approximating k-node Connected Subgraphs via Critical Graphs
- Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
This page was built for publication: On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
