Two algorithms for minimum 2-connected \(r\)-hop dominating set

DOI10.1016/j.ipl.2010.08.008zbMath1379.68355OpenAlexW2046498514MaRDI QIDQ1675775

Zhao Zhang, Xiuying Li

Publication date: 3 November 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.08.008

zbMATH Keywords

approximation algorithmswireless sensor networkfault-tolerantunit disk graph\(r\)-hop dominating set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (4)

Making a dominating set of a graph connected ⋮ A heuristic approach for dividing graphs into bi-connected components with a size constraint ⋮ Construction of Minimum Power 3-Connected Subgraph with k Backbone Nodes in Wireless Sensor Networks ⋮ 2-edge connected dominating sets and 2-connected dominating sets of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• A greedy approximation for minimum connected dominating sets
• Algorithms for minimum \(m\)-connected \(k\)-tuple dominating set problem
• Unit disk graphs
• Approximation algorithms for connected dominating sets
• A quick method for finding shortest pairs of disjoint paths
• A PTAS FOR MINIMUM d-HOP UNDERWATER SINK PLACEMENT PROBLEM IN 2-D UNDERWATER SENSOR NETWORKS
• MINIMUM CONNECTED r-HOP k-DOMINATING SET IN WIRELESS NETWORKS
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET

This page was built for publication: Two algorithms for minimum 2-connected \(r\)-hop dominating set