Construction of strongly connected dominating sets in asymmetric multihop wireless networks

DOI10.1016/j.tcs.2008.09.058zbMath1162.68002OpenAlexW2043936605MaRDI QIDQ1006037

Weili Wu, Zhao Zhang, Xiaofeng Gao, Hongwei David Du, Deying Li, Peng-Jun Wan

Publication date: 17 March 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.09.058

zbMATH Keywords

asymmetric wireless networkstrongly connected dominating set

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (11)

Complexity of the maximum leaf spanning tree problem on planar and regular graphs ⋮ Strong minimum energy hierarchical topology in wireless sensor networks ⋮ On constructing strongly connected dominating and absorbing set in 3-dimensional wireless ad hoc networks ⋮ Minimum energy multicast/broadcast routing with reception cost in wireless sensor networks ⋮ Domination parameters of a graph and its complement ⋮ On the \((h,k)\)-domination numbers of iterated line digraphs ⋮ Bounds on the connected domination number of a graph ⋮ The Optimal Design of Low-Latency Virtual Backbones ⋮ Finding minimum weight connected dominating set in stochastic graph based on learning automata ⋮ Approximation and heuristic algorithms for computing backbones in asymmetric ad-hoc networks ⋮ Connected \(k\)-tuple twin domination in de Bruijn and Kautz digraphs

Cites Work

• A greedy approximation for minimum connected dominating sets
• Approximation algorithms for connected dominating sets
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS

This page was built for publication: Construction of strongly connected dominating sets in asymmetric multihop wireless networks