A note on Rooted Survivable Networks

DOI10.1016/j.ipl.2009.07.011zbMath1206.68039OpenAlexW1987353362MaRDI QIDQ990935

Zeev Nutov

Publication date: 1 September 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.07.011

zbMATH Keywords

network designapproximation algorithmsrooted node-connectivity

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Approximation algorithms (68W25)

Related Items (5)

Survivable network activation problems ⋮ A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems ⋮ An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem ⋮ An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity ⋮ Unnamed Item

Cites Work

• A factor 2 approximation algorithm for the generalized Steiner network problem
• Tight approximation algorithm for connectivity augmentation problems
• Inapproximability of survivable networks
• One for the price of two: a unified approach for approximating covering problems
• Approximating rooted connectivity augmentation problems
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• Approximation Algorithms for Network Design with Metric Costs
• A Graph Reduction Step Preserving Element-Connectivity and Applications
• Approximating Node-Connectivity Augmentation Problems
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• Approximation Algorithms for Directed Steiner Problems
• Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
• An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A note on Rooted Survivable Networks