Improved approximation algorithms for single-tiered relay placement
From MaRDI portal
Publication:266064
DOI10.1007/s10878-014-9823-0zbMath1343.90019OpenAlexW2113181958MaRDI QIDQ266064
Benjamin Grimmer, Satyajayant Misra, Gruia Călinescu, Weiyi Zhang, Sutep Tongngam, Guoliang Xue
Publication date: 13 April 2016
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-014-9823-0
Communication networks in operations research (90B18) Approximation methods and heuristics in mathematical programming (90C59)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Steiner tree problem with minimum number of Steiner points and bounded edge-length
- Relay placement for fault tolerance in wireless networks in higher dimensions
- Wireless network design via 3-decompositions
- An application of submodular flows
- A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points
- Low-degree minimum spanning trees
- An 11/6-approximation algorithm for the network Steiner problem
- Low-degree minimal spanning trees in normed spaces
- Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Improved Approximation Algorithms for Relay Placement
- Thek-Steiner Ratio in Graphs
- Relay Node Placement in Wireless Sensor Networks
- A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
- Improved Approximation Algorithms for Uniform Connectivity Problems
- Approximations for Steiner trees with minimum number of Steiner points