Algorithm of digraph connected dominating set
Wenyu Gao · Computer Engineering and Applications Journal · 2010
The problem of connected dominating set in digraph is defined.A reduction rule for this problem is designed.Reduction rules can reduce the size of original digraph;then an approximation algorithm is designed to find a connected dominating set in the reduced digraph;finally,optimization rule is used to cut down the size of connected dominating set.Simulations in different random digraphs show that these rules and algorithms are effective.