Approximating subset k-connectivity problems

DOI10.1007/978-3-642-29116-6_2zbMATH Open1242.68370OpenAlexW1752264143MaRDI QIDQ2896372FDOQ2896372

Authors: Zeev Nutov 

Publication date: 16 July 2012

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

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

Recommendations

• Approximating subset \(k\)-connectivity problems
• Improved approximation algorithms for min-cost connectivity augmentation problems
• Improved approximation algorithms for minimum cost node-connectivity augmentation problems
• Approximating node connectivity problems via set covers
• Approximating rooted connectivity augmentation problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Connectivity (05C40)

Cited In (16)

• Approximating minimum-cost edge-covers of crossing biset-families
• An almost \(O(\log k)\)-approximation for \(k\)-connected subgraphs
• Approximating \(k\)-connected \(m\)-dominating sets
• Approximating rooted connectivity augmentation problems
• Computing connected-\(k\)-subgraph cover with connectivity requirement
• 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
• Approximating minimum-cost connectivity problems via uncrossable bifamilies
• Approximating subset \(k\)-connectivity problems
• Physical ZKP for connected spanning subgraph: applications to bridges puzzle and other problems
• Approximating \(k\)-generalized connectivity via collapsing HSTs
• Approximation Algorithms and Hardness Results for Labeled Connectivity Problems
• On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• Approximating rooted connectivity augmentation problems

This page was built for publication: Approximating subset \(k\)-connectivity problems

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