Inapproximability of survivable networks

DOI10.1016/j.tcs.2009.01.036zbMath1168.68036OpenAlexW2019123979MaRDI QIDQ1019191

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

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

Related Items (12)

Improved approximation algorithms for minimum cost node-connectivity augmentation problems ⋮ Approximating subset \(k\)-connectivity problems ⋮ Approximating minimum-cost edge-covers of crossing biset-families ⋮ Approximating node-connectivity augmentation problems ⋮ A \(4+\epsilon\) approximation for \(k\)-connected subgraphs ⋮ Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems ⋮ Approximating survivable networks with \(\beta \)-metric costs ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ A note on Rooted Survivable Networks ⋮ Approximating fault-tolerant group-Steiner problems ⋮ Unnamed Item ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Tight approximation algorithm for connectivity augmentation problems
• Approximating the weight of shallow Steiner trees
• Minimal edge-coverings of pairs of sets
• Approximating rooted connectivity augmentation problems
• Design networks with bounded pairwise distance
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• Approximation Algorithms for Directed Steiner Problems

This page was built for publication: Inapproximability of survivable networks