Approximation algorithms for minimum-cost k-(S,T) connected digraphs
DOI10.1137/100818728zbMATH Open1278.05114OpenAlexW1990981902MaRDI QIDQ2870515FDOQ2870515
Authors: B. Laekhanukit, Joseph Cheriyan 
Publication date: 21 January 2014
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/100818728
Recommendations
- Approximating node connectivity problems via set covers
- An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph
- Approximation algorithm for \(k\)-node connected subgraphs via critical graphs
- scientific article; zbMATH DE number 1670542
- An \(O(\log^2{k})\)-approximation algorithm for the \(k\)-vertex connected spanning subgraph problem
network designgraph connectivitydirected Steiner treerooted connectivity\(k\)-vertex connected spanning subgraphs
Programming involving graphs or networks (90C35) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Approximation algorithms (68W25) Flows in graphs (05C21) Connectivity (05C40)
Cited In (9)
- Approximating minimum-cost edge-covers of crossing biset-families
- An approximation algorithm for minimum-cost vertex-connectivity problems
- Improved approximation algorithms for minimum cost node-connectivity augmentation problems
- Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
- Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs
- Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
- An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
- Approximating minimum-cost connected \(T\)-joins
- On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
This page was built for publication: Approximation algorithms for minimum-cost \(k\)-\((S,T)\) connected digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2870515)
