Approximation Algorithms for Minimum-Cost $k\hbox{-}(S,T)$ Connected Digraphs

DOI10.1137/100818728zbMath1278.05114OpenAlexW1990981902MaRDI QIDQ2870515

Bundit 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) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Flows in graphs (05C21)

Related Items (4)

Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ Approximating minimum-cost edge-covers of crossing biset-families ⋮ An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs

This page was built for publication: Approximation Algorithms for Minimum-Cost $k\hbox{-}(S,T)$ Connected Digraphs