Reduction Algorithm for Minimum Connected Dominating Set Problem
Wenyu Gao · Jisuanji gongcheng · 2011
By analyzing the dominant constraints and connectivity constraints of connected dominating set,two reduction rules for minimum connected dominating set in simple connected graph is proposed.These rules can find out some required nodes and delete some redundant nodes in advance through classification of neighbors of any node,and through finding cut nodes in graph,thus reducing the size of the original problem.These reduction rules are proved theoretically and tested by random simulations.