Minimum connected dominating sets and maximal independent sets in unit disk graphs
From MaRDI portal
Publication:818109
DOI10.1016/j.tcs.2005.08.037zbMath1086.68107OpenAlexW2093381928WikidataQ60402829 ScholiaQ60402829MaRDI QIDQ818109
Weili Wu, Yingshu Li, Scott C.-H. Huang, Xiao-Hua Jia, Hongwei David Du
Publication date: 24 March 2006
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2005.08.037
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 (46)
An approximation algorithm for maximum weight budgeted connected set cover ⋮ Making a dominating set of a graph connected ⋮ On constructing strongly connected dominating and absorbing set in 3-dimensional wireless ad hoc networks ⋮ Unnamed Item ⋮ Approximation algorithms for load-balanced virtual backbone construction in wireless sensor networks ⋮ A new bound on maximum independent set and minimum connected dominating set in unit disk graphs ⋮ Improved algorithms in directional wireless sensor networks ⋮ A greedy algorithm for the fault-tolerant connected dominating set in a general graph ⋮ New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs ⋮ A better approximation for constructing virtual backbone in 3D wireless ad-hoc networks ⋮ Distributed connected dominating sets in unit square and disk graphs ⋮ COMBINATORIAL PROPERTIES FOR A CLASS OF SIMPLICIAL COMPLEXES EXTENDED FROM PSEUDO-FRACTAL SCALE-FREE WEB ⋮ Constructing weakly connected dominating set for secure clustering in distributed sensor network ⋮ Distributed dominating sets in interval graphs ⋮ Colored spanning graphs for set visualization ⋮ Research on gateway deployment of WMN based on maximum coupling subgraph and PSO algorithm ⋮ The connected disk covering problem ⋮ On the Power of Lookahead in Greedy Scheme for Finding a Minimum CDS for Unit Disk Graphs ⋮ Improved solution to data gathering with mobile mule ⋮ Wireless networking, dominating and packing ⋮ Minimum average routing path clustering problem in multi-hop 2-D underwater sensor networks ⋮ Computing Minimum k-Connected m-Fold Dominating Set in General Graphs ⋮ Locating battery charging stations to facilitate almost shortest paths ⋮ Tighter approximation bounds for minimum CDS in unit disk graphs ⋮ Routing-efficient CDS construction in disk-containment graphs ⋮ On the recognition of unit disk graphs and the distance geometry problem with ranges ⋮ ALGORITHMS FOR MINIMUM CONNECTED CAPACITATED DOMINATING SET PROBLEM ⋮ The wake up dominating set problem ⋮ The minimum weakly connected independent set problem: polyhedral results and branch-and-cut ⋮ A SELF-STABILIZING DISTRIBUTED APPROXIMATION ALGORITHM FOR THE MINIMUM CONNECTED DOMINATING SET ⋮ An exact algorithm for minimum CDS with shortest path constraint in wireless networks ⋮ TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET ⋮ Algorithms for minimum \(m\)-connected \(k\)-tuple dominating set problem ⋮ 2-edge connected dominating sets and 2-connected dominating sets of a graph ⋮ Message and time efficient multi-broadcast schemes ⋮ Some results for the two disjoint connected dominating sets problem ⋮ An efficient connected dominating set algorithm in WSNS based on the induced tree of the crossed cube ⋮ Connected Domination ⋮ ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS ⋮ The complexity of symmetric connectivity in directional wireless sensor networks ⋮ Super domination in trees ⋮ A PTAS for Weak Minimum Routing Cost Connected Dominating Set of Unit Disk Graph ⋮ Connected \(k\)-tuple twin domination in de Bruijn and Kautz digraphs ⋮ On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm ⋮ Combinatorial properties of Farey graphs ⋮ SPANNING PROPERTIES OF GRAPHS INDUCED BY DIRECTIONAL ANTENNAS
Cites Work
This page was built for publication: Minimum connected dominating sets and maximal independent sets in unit disk graphs
