Greedy Algorithms for Minimum Connected Dominating Set Problems
To solve connected dominating problem, it is necessary to find minimum connected dominating set (MCDS for short).However, to find MCDS is NP-hardness. So, a graph model called interval graph is constructed from nodes of related network. Two greedy algorithms with linear (or polynomial time) are used to find MCDS on proper interval graph (or interval graph), and have 1 approximation ratio on the graphs. And spanning trees are constructed and used to validate the correctness and effectiveness of corresponding algorithms.
CDS MCDS interval graphs greedy algorithm spanning tree
Deren Yang Xiaofeng Wang
College of Science Ningxia Medical University Yinchuan, China College of Computer Science Guizhou University Guiyang, China
国际会议
The 10th International Conference on Intelligent Technologies(第十届智慧科技国际会议 InTech09)
桂林
英文
643-646
2009-12-12（万方平台首次上网日期，不代表论文的发表时间）