A note on Rooted Survivable Networks

DOI10.1016/J.IPL.2009.07.011MaRDI QIDQ990935zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmsnetwork designrooted node-connectivity

Mathematics Subject Classification ID

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

Recommendations

• Inapproximability of Survivable Networks
• Inapproximability of survivable networks
• An almost \(O(\log k)\)-approximation for \(k\)-connected subgraphs
• scientific article; zbMATH DE number 1003253
• An efficient approximation algorithm for the survivable network design problem

Cites work

• scientific article; zbMATH DE number 1003253 (Why is no real title available?)
• scientific article; zbMATH DE number 5485528 (Why is no real title available?)
• A Graph Reduction Step Preserving Element-Connectivity and Applications
• A factor 2 approximation algorithm for the generalized Steiner network problem
• An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
• An almost \(O(\log k)\)-approximation for \(k\)-connected subgraphs
• Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
• Approximating Node-Connectivity Augmentation Problems
• Approximating connectivity augmentation problems
• Approximating rooted connectivity augmentation problems
• Approximation Algorithms for Directed Steiner Problems
• Approximation Algorithms for Network Design with Metric Costs
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• Inapproximability of survivable networks
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• One for the price of two: a unified approach for approximating covering problems
• Single-sink network design with vertex connectivity requirements
• Tight approximation algorithm for connectivity augmentation problems

Cited in

(10)

• A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems
• Inapproximability of Survivable Networks
• An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
• Erratum: ``Approximating minimum-cost connectivity problems via uncrossable bifamilies
• An almost \(O(\log k)\)-approximation for \(k\)-connected subgraphs
• An improved approximation algorithm for minimum-cost subset \(k\)-connectivity (extended abstract)
• Survivable network activation problems
• Inapproximability of survivable networks
• scientific article; zbMATH DE number 5588965 (Why is no real title available?)
• scientific article; zbMATH DE number 7053371 (Why is no real title available?)

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

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