Inapproximability of Survivable Networks

DOI10.1007/978-3-540-85363-3_12MaRDI QIDQ3541792zbMATH OpenOpenAlexFDO

Authors Yuval Lando, Zeev Nutov

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_12

Mathematics Subject Classification ID

Connectivity (05C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Inapproximability of survivable networks
• scientific article; zbMATH DE number 1947057
• An efficient approximation algorithm for the survivable network design problem
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• A note on Rooted Survivable Networks

Cited in

(11)

• Inapproximability of survivable networks
• Approximability of capacitated network design
• Survivable network design: the capacitated minimum spanning network problem
• Approximability of capacitated network design
• scientific article; zbMATH DE number 1947057 (Why is no real title available?)
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree
• A note on iterated rounding for the survivable network design problem
• On survivable set connectivity
• The k-path tree matroid and its applications to survivable network design
• A note on Rooted Survivable Networks

This page was built for publication: Inapproximability of Survivable Networks

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