A primal-dual approximation algorithm for the survivable network design problem in hypergraphs

DOI10.1016/S0166-218X(02)00201-9zbMath1012.68227OpenAlexW2037625746MaRDI QIDQ1861578

Toshihide Ibaraki, Liang Zhao, Hiroshi Nagamochi

Publication date: 9 March 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00201-9

zbMATH Keywords

graphhypergraphapproximation algorithmprimal dual methodhyperedgessurvivable network designproblem

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items

Unnamed Item, Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems

Cites Work

• An approximation algorithm for minimum-cost vertex-connectivity problems
• A factor 2 approximation algorithm for the generalized Steiner network problem
• The primal-dual method for approximation algorithms
• Erratum: An approximation algorithm for minimum-cost vertex-connectivity problems
• A primal-dual approximation algorithm for generalized Steiner network problems
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• Maximal Flow Through a Network
• A new approach to the maximum-flow problem
• A General Approximation Technique for Constrained Forest Problems
• Unnamed Item
• Unnamed Item