A note on Rooted Survivable Networks

DOI10.1016/J.IPL.2009.07.011zbMATH Open1206.68039OpenAlexW1987353362MaRDI QIDQ990935FDOQ990935

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

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

zbMATH Keywords

approximation algorithmsnetwork designrooted node-connectivity

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems
• Title not available (Why is that?)
• An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity
• Title not available (Why is that?)
• An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
• Survivable network activation problems

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)