Minimum connected dominating sets in finite graphs

MaRDI QIDQ712285zbMATH OpenFDO

Authors Le Cong Thanh

Publication date 28 October 2010

Published in Vietnam Journal of Mathematics (Search for Journal in Brave)

Full work available at URL http://www.math.ac.vn/publications/vjm/VJM_38/157.htm

zbMATH Keywords

greedy algorithmdominating setperformance ratio

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Approximation algorithms for connected dominating sets
• Approximation algorithms for connected dominating sets
• Greedy approximation for the minimum connected dominating set with labeling
• A greedy approximation for minimum connected dominating sets
• Minimum connected dominating sets of random cubic graphs

Cited in

(17)

• Greedy approximation for the minimum connected dominating set with labeling
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Near-optimal dominating sets in dense random graphs in polynomial expected time
• Average-case complexity of a branch-and-bound algorithm for \textsc{Min Dominating Set}
• Approximating the minimum independent dominating set in perturbed graphs
• A greedy approximation for minimum connected dominating sets
• scientific article; zbMATH DE number 1875441 (Why is no real title available?)
• scientific article; zbMATH DE number 5131681 (Why is no real title available?)
• The expected size of the Rule \(k\) dominating set
• A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS
• Dominating problems in swapped networks
• The Minset-Poset Approach to Representations of Graph Connectivity
• Minimum connected dominating sets of random cubic graphs
• Minimum 2-dominating sets in regular graphs
• Near-optimal dominating sets via random sampling
• scientific article; zbMATH DE number 3896296 (Why is no real title available?)
• A unified greedy approximation for several dominating set problems

This page was built for publication: Minimum connected dominating sets in finite graphs

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