An $O(\log^2{k})$-Approximation Algorithm for the $k$-Vertex Connected Spanning Subgraph Problem
From MaRDI portal
Publication:4907576
DOI10.1137/110855910zbMath1257.68147OpenAlexW2058521212MaRDI QIDQ4907576
Jittat Fakcharoenphol, Bundit 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
approximation algorithm\(k\)-outconnected subgraphconnected spanning subgraph problemFrank-Tardos algorithm
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)
Related Items (9)
Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ Unnamed Item ⋮ An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem ⋮ A \(4+\epsilon\) approximation for \(k\)-connected subgraphs ⋮ 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 rooted \(k\)-connectivity problems in quasi-bipartite digraphs
This page was built for publication: An $O(\log^2{k})$-Approximation Algorithm for the $k$-Vertex Connected Spanning Subgraph Problem
