On minimum \(m\)-connected \(k\)-dominating set problem in unit disc graphs

DOI10.1007/s10878-007-9124-yzbMath1160.05337OpenAlexW2038841453MaRDI QIDQ1016039

Xiao-Dong Hu, Wei-Ping Shang, Frances F. Yao, Peng-Jun Wan

Publication date: 4 May 2009

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-007-9124-y

zbMATH Keywords

approximation algorithmwireless sensor networksunit disc graph\(k\)-dominating set\(m\)-connectivity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (11)

Approximate event detection over multi-modal sensing data ⋮ Polynomial time approximation schemes for minimum disk cover problems ⋮ A greedy algorithm for the fault-tolerant connected dominating set in a general graph ⋮ Construction of minimum edge-fault tolerant connected dominating set in a general graph ⋮ Liar's domination in unit disk graphs ⋮ Computing Minimum k-Connected m-Fold Dominating Set in General Graphs ⋮ Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set ⋮ Approximation algorithms for highly connected multi-dominating sets in unit disk graphs ⋮ Sensor network topology design and analysis for efficient data gathering by a mobile mule ⋮ A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem ⋮ Tractable connected domination for restricted bipartite graphs

Cites Work

• Unnamed Item
• Algorithms for minimum \(m\)-connected \(k\)-tuple dominating set problem
• On constructing \(k\)-connected \(k\)-dominating set in wireless ad hoc and sensor networks
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: On minimum \(m\)-connected \(k\)-dominating set problem in unit disc graphs