Approximating Survivable Networks with Minimum Number of Steiner Points

DOI10.1007/978-3-642-18318-8_14zbMath1314.68399arXiv1304.7571OpenAlexW1498454938MaRDI QIDQ3075458

Lior Kamma, Zeev Nutov

Publication date: 15 February 2011

Published in: Networks, Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1304.7571

zbMATH Keywords

approximation algorithmssensor networksnode-connectivityunit disc graphsunit-disc graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Approximation algorithms (68W25) Connectivity (05C40) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (5)

Approximating Steiner Trees and Forests with Minimum Number of Steiner Points ⋮ Survivable minimum bottleneck networks ⋮ g-Steiner, co-Steiner and Normal Points of Bounded Euclidean Submanifolds ⋮ Approximating Steiner trees and forests with minimum number of Steiner points ⋮ Relay placement for two-connectivity

Cites Work

• Approximating minimum-power degree and connectivity problems
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Wireless network design via 3-decompositions
• An application of submodular flows
• Low-degree minimum spanning trees
• Approximating subset \(k\)-connectivity problems
• An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
• Approximating Steiner Networks with Node-Weights
• Approximating k-node Connected Subgraphs via Critical Graphs
• THE MAXIMUM CONNECTIVITY OF A GRAPH

This page was built for publication: Approximating Survivable Networks with Minimum Number of Steiner Points