Parameterized algorithms for survivable network design with uniform demands

MaRDI QIDQ4608076zbMATH OpenFDO

Authors Manu Basavaraju, Kristine Vitting Klinkby, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi, Jørgen Bang-Jensen

Publication date 15 March 2018

Full work available at URL http://dl.acm.org/citation.cfm?id=3175484

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Recommendations

• Fast exact algorithms for survivable network design with uniform requirements
• Survivable network design with degree or order constraints
• An \(O(k^3\log n)\)-approximation algorithm for vertex-connectivity survivable network design
• A PTAS for three-edge-connected survivable network design in planar graphs
• scientific article; zbMATH DE number 1947057

Cited in

(9)

• Complexity of column generation in network design with path-based survivability mechanisms
• Survivable network design with demand uncertainty
• The parameterized complexity of the survivable network design problem
• Fast exact algorithms for survivable network design with uniform requirements
• Fast exact algorithms for survivable network design with uniform requirements
• On the fixed-parameter tractability of the maximum connectivity improvement problem
• The parameterized complexity of the survivable network design problem
• Path-contractions, edge deletions and connectivity preservation
• Fast Approximation Algorithms for the Generalized Survivable Network Design Problem

This page was built for publication: Parameterized algorithms for survivable network design with uniform demands

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