Algorithms for minimum m-connected k-tuple dominating set problem

DOI10.1016/J.TCS.2007.04.035MaRDI QIDQ995580zbMATH OpenOpenAlexFDO

Authors Weiping Shang, Peng-Jun Wan, Frances F. Yao, Xiaodong 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 algorithmwireless sensor networksconnected dominating set\(k\)-vertex connectivity

Mathematics Subject Classification ID

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

Recommendations

• Algorithms for Minimum m-Connected k-Dominating Set Problem
• On minimum \(m\)-connected \(k\)-dominating set problem in unit disc graphs
• On the construction of \(k\)-connected \(m\)-dominating sets in wireless networks
• A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem
• On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs

Cites work

• scientific article; zbMATH DE number 1792607 (Why is no real title available?)
• Depth-First Search and Linear Graph Algorithms
• Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
• Minimum connected dominating sets and maximal independent sets in unit disk graphs

Cited in

(22)

• Liar's dominating set problem on unit disk graphs
• Approximation algorithms for load-balanced virtual backbone construction in wireless sensor networks
• A polyhedral view to a generalization of multiple domination
• TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET
• On the construction of \(k\)-connected \(m\)-dominating sets in wireless networks
• Probabilistic analysis of upper bounds for 2-connected distance \(k\)-dominating sets in graphs
• A greedy algorithm for the fault-tolerant connected dominating set in a general graph
• Load-balanced virtual backbone construction for wireless sensor networks
• On approximating (connected) 2-edge dominating set by a tree
• On approximating (connected) 2-edge dominating set by a tree
• On the (h,k)-domination numbers of iterated line digraphs
• The optimal design of low-latency virtual backbones
• Polynomial time approximation schemes for minimum disk cover problems
• Connected \(k\)-tuple twin domination in de Bruijn and Kautz digraphs
• Two algorithms for minimum 2-connected r-hop dominating set
• Algorithms for minimum connected capacitated dominating set problem
• Algorithms for the minimum weight k-fold (connected) dominating set problem
• On constructing \(k\)-connected \(k\)-dominating set in wireless ad hoc and sensor networks
• Heuristics for \(k\)-domination models of facility location problems in street networks
• MINIMUM CONNECTED r-HOP k-DOMINATING SET IN WIRELESS NETWORKS
• On minimum \(m\)-connected \(k\)-dominating set problem in unit disc graphs
• Algorithms for Minimum m-Connected k-Dominating Set Problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q995580)