Inapproximability of survivable networks

DOI10.1016/J.TCS.2009.01.036MaRDI QIDQ1019191zbMATH OpenOpenAlexFDO

Authors Yuval Lando, Zeev Nutov

Publication date 28 May 2009

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2009.01.036

zbMATH Keywords

hardness of approximationdirected Steiner tree\(k\)-connected subgraphsurvivable network design problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

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

Cites work

• scientific article; zbMATH DE number 5485528 (Why is no real title available?)
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• An almost \(O(\log k)\)-approximation for \(k\)-connected subgraphs
• Approximating connectivity augmentation problems
• Approximating rooted connectivity augmentation problems
• Approximating the weight of shallow Steiner trees
• Approximation Algorithms for Directed Steiner Problems
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Design networks with bounded pairwise distance
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• Minimal edge-coverings of pairs of sets
• Tight approximation algorithm for connectivity augmentation problems

Cited in

(21)

• Approximating minimum-cost edge-covers of crossing biset-families
• Approximating rooted Steiner networks
• A note on Rooted Survivable Networks
• scientific article; zbMATH DE number 1947057 (Why is no real title available?)
• On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
• Approximating survivable networks with \(\beta \)-metric costs
• Improved approximation algorithms for minimum cost node-connectivity augmentation problems
• A 4+ approximation for k-connected subgraphs
• Improved approximation algorithms for min-cost connectivity augmentation problems
• A note on iterated rounding for the survivable network design problem
• Approximating subset \(k\)-connectivity problems
• Approximating node-connectivity augmentation problems
• Approximability of capacitated network design
• Inapproximability of Survivable Networks
• Survivable network design: the capacitated minimum spanning network problem
• scientific article; zbMATH DE number 7053371 (Why is no real title available?)
• Approximating fault-tolerant group-Steiner problems
• On survivable set connectivity
• On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• On the approximability of some network design problems

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 Q1019191)