An O(^2k)-approximation algorithm for the k-vertex connected spanning subgraph problem
DOI10.1137/110855910zbMATH Open1257.68147OpenAlexW2058521212MaRDI QIDQ4907576FDOQ4907576
Authors: Jittat Fakcharoenphol, B. Laekhanukit 
Publication date: 4 February 2013
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/110855910
Recommendations
- An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph
- A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
- An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
- A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs
- Approximation algorithm for \(k\)-node connected subgraphs via critical graphs
approximation algorithm\(k\)-outconnected subgraphconnected spanning subgraph problemFrank-Tardos algorithm
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Connectivity (05C40)
Cited In (17)
- An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph
- Title not available (Why is that?)
- Approximation algorithms for minimum-cost \(k\)-\((S,T)\) connected digraphs
- On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
- Improved approximation algorithms for minimum cost node-connectivity augmentation problems
- Improved approximation algorithms for min-cost connectivity augmentation problems
- A \(4+\epsilon\) approximation for \(k\)-connected subgraphs
- An improved approximation algorithm for minimum-cost subset \(k\)-connectivity (extended abstract)
- Title not available (Why is that?)
- Title not available (Why is that?)
- An \(O(k^3\log n)\)-approximation algorithm for vertex-connectivity survivable network design
- 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
- On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
- Approximation algorithm for \(k\)-node connected subgraphs via critical graphs
- A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms
- Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
This page was built for publication: An \(O(\log^2{k})\)-approximation algorithm for the \(k\)-vertex connected spanning subgraph problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4907576)
