Approximating survivable networks with \(\beta \)-metric costs

DOI10.1016/j.jda.2010.11.002zbMath1217.90153OpenAlexW1978156633MaRDI QIDQ553954

Johnny David, Zeev Nutov

Publication date: 29 July 2011

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2010.11.002

zbMATH Keywords

network designgraph connectivityapproximation algorithmsmetric costs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (1)

Small \(\ell\)-edge-covers in \(k\)-connected graphs

Cites Work

• Unnamed Item
• On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality
• On \(k\)-connectivity problems with sharpened triangle inequality
• Inapproximability of survivable networks
• Approximating node connectivity problems via set covers
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• Design networks with bounded pairwise distance
• Approximation Algorithms for Network Design with Metric Costs
• A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
• 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
• THE MAXIMUM CONNECTIVITY OF A GRAPH

This page was built for publication: Approximating survivable networks with \(\beta \)-metric costs