期刊刊名：管理科學與統計決策 　 卷期：7卷1期

篇名出版日期：2010年3月1日

作者：Deren Yang,Xiaofeng Wang

語言：English

關鍵字：CDS,MCDS,interval graphs,greedy algorithm,spanning tree

被點閱次數：0次

閱讀時間：0sec

摘要：
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.

　　　　　[全文下載]