A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs

DOI10.1007/978-3-540-85363-3_19zbMath1159.68676OpenAlexW1574619705MaRDI QIDQ5900474

Mohammad Ali Safari, Mohammad R. Salavatipour

Publication date: 27 November 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85363-3_19

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items

Pruning 2-connected graphs ⋮ On approximating the \(d\)-girth of a graph ⋮ On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem ⋮ On Approximating the d-Girth of a Graph

Cites Work

• Unnamed Item
• Unnamed Item
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A constant-factor approximation algorithm for the \(k\)-MST problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
• Survivable network design with degree or order constraints
• Approximation algorithms for network design with metric costs
• Saving an epsilon
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• Spanning Trees—Short or Small
• The dense \(k\)-subgraph problem