On connected domination in unit ball graphs

DOI10.1007/s11590-010-0211-0zbMath1220.90148OpenAlexW1987607815MaRDI QIDQ537633

Sera Kahruman-Anderoglu, Oleksii Ursulenko, Sergiy I. Butenko

Publication date: 20 May 2011

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-010-0211-0

zbMATH Keywords

wireless networksconnected dominating setunit ball graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10)

Related Items

On constructing strongly connected dominating and absorbing set in 3-dimensional wireless ad hoc networks ⋮ A distributed approximation algorithm for the bottleneck connected dominating set problem ⋮ A better approximation for constructing virtual backbone in 3D wireless ad-hoc networks ⋮ Bounds on the domination number of a digraph ⋮ Constrained surface-level gateway placement for underwater acoustic wireless sensor networks ⋮ Wireless networking, dominating and packing ⋮ Linear separation of connected dominating sets in graphs ⋮ A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks

Cites Work

• Unnamed Item
• Unit disk graphs
• Unit disk graph recognition is NP-hard
• Approximation algorithms for connected dominating sets
• Improved bottleneck domination algorithms
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks