Approximating subset k-connectivity problems

DOI10.1007/978-3-642-29116-6_2MaRDI QIDQ2896372zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(16)

• Approximating rooted connectivity augmentation problems
• 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
• A 4+ approximation for k-connected subgraphs
• Improved approximation algorithms for min-cost connectivity augmentation problems
• 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

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)