Algorithms for minimum \(m\)-connected \(k\)-tuple dominating set problem

DOI10.1016/j.tcs.2007.04.035zbMath1188.68359OpenAlexW2108073093MaRDI QIDQ995580

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

Publication date: 3 September 2007

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

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

zbMATH Keywords

approximation algorithmconnected dominating setwireless sensor networks\(k\)-vertex connectivity

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Approximation algorithms (68W25)

Related Items (12)

A polyhedral view to a generalization of multiple domination ⋮ Probabilistic analysis of upper bounds for 2-connected distance \(k\)-dominating sets in graphs ⋮ On approximating (connected) 2-edge dominating set by a tree ⋮ Two algorithms for minimum 2-connected \(r\)-hop dominating set ⋮ Heuristics for \(k\)-domination models of facility location problems in street networks ⋮ Polynomial time approximation schemes for minimum disk cover problems ⋮ Liar's dominating set problem on unit disk graphs ⋮ On the \((h,k)\)-domination numbers of iterated line digraphs ⋮ On Approximating (Connected) 2-Edge Dominating Set by a Tree ⋮ On minimum \(m\)-connected \(k\)-dominating set problem in unit disc graphs ⋮ MINIMUM CONNECTED r-HOP k-DOMINATING SET IN WIRELESS NETWORKS ⋮ Connected \(k\)-tuple twin domination in de Bruijn and Kautz digraphs

Cites Work

• Unnamed Item
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: Algorithms for minimum \(m\)-connected \(k\)-tuple dominating set problem