An O(^2k)-approximation algorithm for the k-vertex connected spanning subgraph problem

DOI10.1137/110855910MaRDI QIDQ4907576zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

approximation algorithm\(k\)-outconnected subgraphconnected spanning subgraph problemFrank-Tardos algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Connectivity (05C40)

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

Cited in

(17)

• scientific article; zbMATH DE number 1757950 (Why is no real title available?)
• 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
• An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph
• Improved approximation algorithms for min-cost connectivity augmentation problems
• An improved approximation algorithm for minimum-cost subset \(k\)-connectivity (extended abstract)
• An \(O(k^3\log n)\)-approximation algorithm for vertex-connectivity survivable network design
• Approximation algorithms for minimum-cost \(k\)-\((S,T)\) connected digraphs
• scientific article; zbMATH DE number 7651209 (Why is no real title available?)
• Improved approximation algorithms for minimum cost node-connectivity augmentation problems
• On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
• A \(4+\epsilon\) approximation for \(k\)-connected subgraphs
• Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
• Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
• scientific article; zbMATH DE number 2038725 (Why is no real title available?)

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)