Greedy Algorithms for Minimum Connected Dominating Set Problems

被引：0

作者：

Yang, Deren ^{[1
]}

Wang, Xiaofeng ^{[1
]}

机构：

[1] Ningxia Med Univ, Coll Sci, Yinchuan, Peoples R China

来源：

PROCEEDING OF THE 10TH INTERNATIONAL CONFERENCE ON INTELLIGENT TECHNOLOGIES | 2009年

关键词：

CDS; MCDS; interval graphs; greedy algorithm; spanning tree; TRACKING MOBILE USERS; APPROXIMATION;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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.

引用

页码：643 / 646

页数：4

共 10 条

[1] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[2] Recognizing and representing proper interval graphs in parallel using merging and sorting
Bang-Jensen, Jorgen
Huang, Jing
Ibarra, Louis
[J]. DISCRETE APPLIED MATHEMATICS, 2007, 155 (04) : 442 - 456
[3] Distributed algorithms for connected domination in wireless networks
Gandhi, Rajiv
Parthasarathy, Srinivasan
[J]. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2007, 67 (07) : 848 - 862
[4] A new distributed approximation algorithm for constructing minimum connected dominating set in wireless ad hoc networks
Gao, B
Yang, YH
Ma, HY
[J]. INTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, 2005, 18 (08) : 743 - 762
[5] Greedy algorithms for tracking mobile users in special mobility graphs
Olariu, S
Pinotti, MC
Wilson, L
[J]. DISCRETE APPLIED MATHEMATICS, 2002, 121 (1-3) : 215 - 227
[6] A linear time recognition algorithm for proper interval graphs
Panda, BS
Das, SK
[J]. INFORMATION PROCESSING LETTERS, 2003, 87 (03) : 153 - 161
[7] On the interval completion of chordal graphs
Peng, SL
Chen, CK
[J]. DISCRETE APPLIED MATHEMATICS, 2006, 154 (06) : 1003 - 1010
[8] Pinotti MC, 1998, P ANN HICSS, P666, DOI 10.1109/HICSS.1998.649268
[9] A greedy approximation for minimum connected dominating sets
Ruan, L
Du, HW
Jia, XH
Wu, WL
Li, YS
Ko, K
[J]. THEORETICAL COMPUTER SCIENCE, 2004, 329 (1-3) : 325 - 330
[10] Wan PJ, 2002, IEEE INFOCOM SER, P1597, DOI 10.1109/INFCOM.2002.1019411

← 1 →