Improved approximation algorithms for single-tiered relay placement

DOI10.1007/S10878-014-9823-0MaRDI QIDQ266064zbMATHOpenAlexFDO

Authors Gruia Calinescu, Benjamin Grimmer, Satyajayant Misra, Sutep Tongngam, Guoliang Xue, Weiyi Zhang

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 algorithmbiconnectivitySteiner pointswireless network

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Communication networks in operations research (90B18)

Recommendations

• Relay placement for two-connectivity
• Computing and Combinatorics
• Relay node placement in two-tiered wireless sensor networks with base stations

Cites work

• scientific article; zbMATH DE number 437545 (Why is no real title available?)
• scientific article; zbMATH DE number 3884935 (Why is no real title available?)
• A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
• A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points
• An 11/6-approximation algorithm for the network Steiner problem
• An application of submodular flows
• Approximations for Steiner trees with minimum number of Steiner points
• Connections in combinatorial optimization
• Improved Approximation Algorithms for Uniform Connectivity Problems
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• Low-degree minimal spanning trees in normed spaces
• Low-degree minimum spanning trees
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Relay Node Placement in Wireless Sensor Networks
• Relay placement for fault tolerance in wireless networks in higher dimensions
• Steiner tree problem with minimum number of Steiner points and bounded edge-length
• Thek-Steiner Ratio in Graphs
• Wireless network design via 3-decompositions

Cited in

(8)

• A survey on relay placement with runtime and approximation guarantees
• Computing and Combinatorics
• Optimal placement of UV-based communications relay nodes
• Relay placement for fault tolerance in wireless networks in higher dimensions
• Trajectory-based multi-hop relay deployment in wireless networks
• Relay placement for two-connectivity
• On optimal placement of relay nodes for reliable connectivity in wireless sensor networks
• Relays: a new approach for the finite departure problem in overlay networks

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q266064)