Additive Approximation for Bounded Degree Survivable Network Design

DOI10.1137/110854461MaRDI QIDQ5408765zbMATH OpenOpenAlexFDO

Authors Lap Chi Lau, Mohit Singh

Publication date 11 April 2014

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/110854461

zbMATH Keywords

linear programmingapproximation algorithmssurvivable network designSteiner forestiterative relaxation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25)

Recommendations

• Additive guarantees for degree-bounded directed network design
• A unified algorithm for degree bounded survivable network design
• A unified algorithm for degree bounded survivable network design
• scientific article; zbMATH DE number 1263260
• An efficient approximation algorithm for the survivable network design problem
• Improved algorithm for degree bounded survivable network design problem
• Strong lower bounds for a survivable network design problem
• Survivable network design problems with weighted degree constraints
• Survivable network design with degree or order constraints
• Approximability of robust network design

Cited in

(13)

• Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements
• The complexity of optimal design of temporally connected graphs
• Approximating bounded-degree spanning trees and connected factors with leaves
• On approximating degree-bounded network design problems
• A unified algorithm for degree bounded survivable network design
• Approximation algorithms for connected graph factors of minimum weight
• A unified algorithm for degree bounded survivable network design
• On approximating degree-bounded network design problems
• Survivable network design with degree or order constraints
• Improved algorithm for degree bounded survivable network design problem
• Additive guarantees for degree-bounded directed network design
• Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
• A Spectral Approach to Network Design

This page was built for publication: Additive Approximation for Bounded Degree Survivable Network Design

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