Improved approximation algorithms for single-tiered relay placement

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

zbMATH Keywords

approximation algorithmwireless networkSteiner pointsbiconnectivity

Mathematics Subject Classification ID

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

This page was built for publication: Improved approximation algorithms for single-tiered relay placement