MINIMUM CONNECTED r-HOP k-DOMINATING SET IN WIRELESS NETWORKS

DOI10.1142/S1793830909000087zbMath1175.05131MaRDI QIDQ3634203

Huiqiang Yang, Lin Liu, Deying Li

Publication date: 23 June 2009

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmwireless networks\(r\)-hop \(k\)-dominating set\(r\)-hop dominatingconnected \(r\)-hop \(k\)-dominating set

Mathematics Subject Classification ID

Applications of graph theory (05C90) Communication networks in operations research (90B18) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (11)

New dominating sets in social networks ⋮ Two algorithms for minimum 2-connected \(r\)-hop dominating set ⋮ Improved linear problem kernel for planar connected dominating set ⋮ A greedy algorithm for the fault-tolerant connected dominating set in a general graph ⋮ Fault-tolerant routing: \(k\)-inconnected many-to-one routing in wireless networks ⋮ On positive influence dominating sets in social networks ⋮ Progress on fault-tolerant locating-dominating sets ⋮ Wireless networking, dominating and packing ⋮ Constructing minimum extended weakly-connected dominating sets for clustering in ad hoc networks ⋮ TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET ⋮ A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem

Cites Work

• Algorithms for minimum \(m\)-connected \(k\)-tuple dominating set problem
• Approximation algorithms for connected dominating sets
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks

This page was built for publication: MINIMUM CONNECTED r-HOP k-DOMINATING SET IN WIRELESS NETWORKS