On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
From MaRDI portal
Publication:6200809
DOI10.1007/S43069-023-00285-6OpenAlexW3088480425WikidataQ129802823 ScholiaQ129802823MaRDI QIDQ6200809
Publication date: 20 February 2024
Published in: SN Operations Research Forum (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s43069-023-00285-6
approximation algorithms\(T\)-intersecting supermodular set functionsmin-cost rooted \(k\)-edge-connectionquasi-bipartite digraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Multi-rooted greedy approximation of directed Steiner trees with applications
- Approximating source location and star survivable network problems
- 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
- Approximating minimum power covers of intersecting families and directed edge-connectivity problems
- Inapproximability of survivable networks
- Rooted \(k\)-connections in digraphs
- Approximating the weight of shallow Steiner trees
- An improved approximation scheme for the Group Steiner Problem
- Prize-Collecting Survivable Network Design in Node-Weighted Graphs
- Polylogarithmic inapproximability
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
- Spider Covers for Prize-Collecting Network Activation 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
- Approximating Rooted Steiner Networks
- 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
- 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
- Approximating Steiner Networks with Node-Weights
- Steiner Tree Approximation via Iterative Randomized Rounding
- Matroids and integrality gaps for hypergraphic steiner tree relaxations
- 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
