Approximation algorithms for minimum-cost k-(S,T) connected digraphs

DOI10.1137/100818728MaRDI QIDQ2870515zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

network designgraph connectivitydirected Steiner treerooted connectivity\(k\)-vertex connected spanning subgraphs

Mathematics Subject Classification ID

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)

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

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)