Relay placement for fault tolerance in wireless networks in higher dimensions

DOI10.1016/j.comgeo.2010.11.002zbMath1208.90038OpenAlexW2025373161MaRDI QIDQ632722

Samir Khuller, Mark A. Shayman, Abhishek Kumar Kashyap

Publication date: 25 March 2011

Published in: Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

fault tolerancenetwork connectivity

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Communication networks in operations research (90B18) Internet topics (68M11)

Related Items

Improved approximation algorithms for single-tiered relay placement ⋮ Approximating Steiner Trees and Forests with Minimum Number of Steiner Points ⋮ Constrained surface-level gateway placement for underwater acoustic wireless sensor networks ⋮ Approximating Steiner trees and forests with minimum number of Steiner points ⋮ Localized fault tolerant algorithm based on node movement freedom degree in flying ad hoc networks ⋮ Relay placement for two-connectivity

Cites Work

• Unnamed Item
• Unnamed Item
• Steiner tree problem with minimum number of Steiner points and bounded edge-length
• An application of submodular flows
• Transitions in geometric minimum spanning trees
• Approximating node connectivity problems via set covers
• A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points
• A matroid approach to finding edge connectivity and packing arborescences
• Low-degree minimum spanning trees
• Improved Approximation Algorithms for Relay Placement
• A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
• A weighted matroid intersection algorithm
• Biconnectivity approximations and graph carvings
• Relay Node Placement in Wireless Sensor Networks
• A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
• A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs
• Improved Approximation Algorithms for Uniform Connectivity Problems
• Computing and Combinatorics
• Approximations for Steiner trees with minimum number of Steiner points