Approximation algorithm for k-node connected subgraphs via critical graphs
DOI10.1145/1007352.1007381zbMATH Open1192.90233OpenAlexW2023660553MaRDI QIDQ3580964FDOQ3580964
Authors: Guy Kortsarz, Zeev Nutov 
Publication date: 15 August 2010
Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1007352.1007381
Recommendations
- Approximating k-node Connected Subgraphs via Critical Graphs
- Approximating node connectivity problems via set covers
- Approximating minimum-cost \(k\)-node connected subgraphs via independence-free graphs
- An \(O(\log^2{k})\)-approximation algorithm for the \(k\)-vertex connected spanning subgraph problem
- An almost \(O(\log k)\)-approximation for \(k\)-connected subgraphs
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
Cited In (8)
- Approximating k-node Connected Subgraphs via Critical Graphs
- Power optimization for connectivity problems
- A derandomized approximation algorithm for the critical node detection problem
- A \(4+\epsilon\) approximation for \(k\)-connected subgraphs
- On the \(L_{\infty}\)-norm of extreme points for crossing supermodular directed network LPs
- Title not available (Why is that?)
- Approximating minimum-cost connected \(T\)-joins
- A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms
This page was built for publication: Approximation algorithm for \(k\)-node connected subgraphs via critical graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3580964)
