Parameterized algorithms for survivable network design with uniform demands

zbMATH Open1403.90559MaRDI QIDQ4608076FDOQ4608076

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

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

Mathematics Subject Classification ID

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

Cited In (8)

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

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)