Approximating k-node Connected Subgraphs via Critical Graphs
From MaRDI portal
Publication:5700579
DOI10.1137/S0097539703435753zbMath1086.68148MaRDI QIDQ5700579
Publication date: 28 October 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Network design and communication in computer systems (68M10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ Approximating subset \(k\)-connectivity problems ⋮ Approximating \(k\)-connected \(m\)-dominating sets ⋮ Survivable network activation problems ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ Approximating minimum-cost edge-covers of crossing biset-families ⋮ An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem ⋮ A \(4+\epsilon\) approximation for \(k\)-connected subgraphs ⋮ An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ On \(k\)-connectivity problems with sharpened triangle inequality ⋮ Approximating Survivable Networks with Minimum Number of Steiner Points ⋮ Approximating minimum-power edge-covers and 2,3-connectivity ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
This page was built for publication: Approximating k-node Connected Subgraphs via Critical Graphs
