An improved approximation algorithm for minimum-cost subset k-connectivity (extended abstract)

DOI10.1007/978-3-642-22006-7_2MaRDI QIDQ3012788zbMATH OpenOpenAlexFDO

Authors B. Laekhanukit

Publication date 6 July 2011

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22006-7_2

Mathematics Subject Classification ID

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

Recommendations

• An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
• An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph
• An \(O(\log^2{k})\)-approximation algorithm for the \(k\)-vertex connected spanning subgraph problem
• scientific article; zbMATH DE number 1817738
• An O(k^3 n)-approximation algorithm for vertex-connectivity survivable network design

Cites work

• A factor 2 approximation algorithm for the generalized Steiner network problem
• A Graph Reduction Step Preserving Element-Connectivity and Applications
• A note on Rooted Survivable Networks
• An approximation algorithm for minimum-cost vertex-connectivity problems
• An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph
• An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
• An improved LP-based approximation for Steiner tree
• An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
• Approximating k-node Connected Subgraphs via Critical Graphs
• Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
• Approximation Algorithms for Network Design with Metric Costs
• Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• scientific article; zbMATH DE number 1003253 (Why is no real title available?)
• scientific article; zbMATH DE number 5485526 (Why is no real title available?)
• scientific article; zbMATH DE number 5485528 (Why is no real title available?)
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems

Cited in

(7)

• Approximating subset \(k\)-connectivity problems
• Approximating minimum-cost \(k\)-node connected subgraphs via independence-free graphs
• Approximating minimum-cost edge-covers of crossing biset-families
• An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph
• An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
• scientific article; zbMATH DE number 7053371 (Why is no real title available?)
• Multi-priority graph sparsification

This page was built for publication: An improved approximation algorithm for minimum-cost subset \(k\)-connectivity (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3012788)