Anonymous Self-Stabilizing Distributed Algorithms for Connected Dominating Set in a Network Graph

被引：0

作者：

Goddard, Wayne ^{[1
]}

Srimani, Pradip K. ^{[1
]}

机构：

[1] Clemson Univ, Sch Comp, Clemson, SC 29634 USA

来源：

IMCIC 2010: INTERNATIONAL MULTI-CONFERENCE ON COMPLEXITY, INFORMATICS AND CYBERNETICS, VOL I (POST-CONFERENCE EDITION) | 2010年

关键词：

APPROXIMATION;

D O I：

暂无

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

A self-stabilizing algorithm is a distributed algorithm where there is neither coordination nor initialization but the network achieves some global state. A connected dominating set (CDS) of a graph is a subset S of the nodes such that the subgraph induced by S is connected and every other node in the graph is adjacent to some node of S. A CDS is suitable as a spine or subset for communication. We provide and analyze two versions of a self-stabilizing algorithm for creating a good CDS. The better version is based on the construction of a breadth-first spanning tree with large internal degree and then discarding the leaves.

引用

页码：356 / 361

页数：6

共 11 条

[1]

Attiya H., 1998, Distributed Computing

[2] An extended localized algorithm for connected dominating set formation in ad hoc wireless networks [J].

Dai, F ;

Wu, J .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2004, 15 (10) :908-920

[3] SELF-STABILIZING SYSTEMS IN SPITE OF DISTRIBUTED CONTROL [J].

DIJKSTRA, EW .

COMMUNICATIONS OF THE ACM, 1974, 17 (11) :643-644

[4] SELF-STABILIZATION OF DYNAMIC-SYSTEMS ASSUMING ONLY READ WRITE ATOMICITY [J].

DOLEV, S ;

ISRAELI, A ;

MORAN, S .

DISTRIBUTED COMPUTING, 1993, 7 (01) :3-16

[5] Random geometric graph diameter in the unit ball [J].

Ellis, Robert B. ;

Martin, Jeremy L. ;

Yan, Catherine .

ALGORITHMICA, 2007, 47 (04) :421-438

[6] Approximation algorithms for connected dominating sets [J].

Guha, S ;

Khuller, S .

ALGORITHMICA, 1998, 20 (04) :374-387

[7]

Jain A, 2005, PDCAT 2005: Sixth International Conference on Parallel and Distributed Computing, Applications and Technologies, Proceedings, P615

[8]

Kamei S., 2007, 2007 IEE INT PAR DIS, P1, DOI [10.1109/IPDPS.2007.370464, DOI 10.1109/IPDPS.2007.370464]

[9]

Kamei S, 2008, LECT NOTES COMPUT SC, V5401, P496, DOI 10.1007/978-3-540-92221-6_31

[10] Distributed construction of connected dominating set in wireless ad hoc networks [J].

Wan, PJ ;

Alzoubi, KM ;

Frieder, O .

MOBILE NETWORKS & APPLICATIONS, 2004, 9 (02) :141-149

← 1 2 →