On rooted k-connectivity problems in quasi-bipartite digraphs
From MaRDI portal
Publication:2117101
DOI10.1007/978-3-030-79416-3_20OpenAlexW3174748938MaRDI QIDQ2117101FDOQ2117101
Authors: Zeev Nutov 
Publication date: 21 March 2022
Full work available at URL: https://arxiv.org/abs/2009.10160
Cites Work
- Approximating the weight of shallow Steiner trees
- Multi-rooted greedy approximation of directed Steiner trees with applications
- Polylogarithmic inapproximability
- Title not available (Why is that?)
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
- Approximation Algorithms for Directed Steiner Problems
- Steiner tree approximation via iterative randomized rounding
- A series of approximation algorithms for the acyclic directed Steiner tree problem
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- Rooted \(k\)-connections in digraphs
- Title not available (Why is that?)
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Matroids and integrality gaps for hypergraphic Steiner tree relaxations
- An improved approximation scheme for the Group Steiner Problem
- Improved approximation algorithms for minimum cost node-connectivity augmentation problems
- Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
- Approximating k-node Connected Subgraphs via Critical Graphs
- Inapproximability of survivable networks
- Tight approximation algorithm for connectivity augmentation problems
- Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
- An \(O(\log^2{k})\)-approximation algorithm for the \(k\)-vertex connected spanning subgraph problem
- Parameters of two-prover-one-round game and the hardness of connectivity problems
- Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems
- A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs
- Approximating Steiner Networks with Node Weights
- Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems
- Approximating source location and star survivable network problems
- Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree
- Prize-collecting survivable network design in node-weighted graphs
- Spider covers for prize-collecting network activation problem
- Title not available (Why is that?)
- \(O(\log^2 k/\log\log k)\)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm
- Title not available (Why is that?)
Cited In (1)
This page was built for publication: On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117101)
