Self-stabilizing algorithms for minimal global powerful alliance sets in graphs

被引：5

作者：

Yahiaoui, Said ^{[1
,2
]}

Belhoul, Yacine ^{[1
,3
]}

Haddad, Mohammed ^{[1
]}

Kheddouci, Hamamache ^{[1
]}

机构：

[1] Univ Lyon 1, LIRIS, CNRS, UMR5205, F-69622 Villeurbanne, France

[2] Univ A Mira, Dept Informat, Bejaia 06000, Algeria

[3] CERIST, Algiers 16030, Algeria

来源：

INFORMATION PROCESSING LETTERS | 2013年 / 113卷 / 10-11期

关键词：

Self-stabilizing algorithms; Graph algorithms; Global powerful alliance; Distributed algorithms;

D O I：

10.1016/j.ipl.2013.03.001

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We propose a self-stabilizing distributed algorithm for the minimal global powerful alliance set problem in an arbitrary graph. Then, we give self-stabilizing algorithms for some generalizations of the problem. Using an unfair distributed scheduler, the proposed algorithms converge in O (mn) moves starting from an arbitrary state. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：365 / 370

页数：6

共 20 条

[1]

[Anonymous], CAN HYDR C P

[2] An efficient self-stabilizing distance-2 coloring algorithm [J].

Blair, Jean R. S. ;

Manne, Fredrik .

THEORETICAL COMPUTER SCIENCE, 2012, 444 :28-39

[3] Powerful alliances in graphs [J].

Brigham, Robert C. ;

Dutton, Ronald D. ;

Haynes, Teresa W. ;

Hedetniemi, Stephen T. .

DISCRETE MATHEMATICS, 2009, 309 (08) :2140-2147

[4]

Dean B.C., 2007, CONGR NUMER CONF J N, V187, P76

[5]

Devismes S., 2011, 2 INT C NETW COMP IC, P30

[6] A SILENT SELF-STABILIZING ALGORITHM FOR FINDING CUT- NODES AND BRIDGES [J].

Devismes, Stephane .

PARALLEL PROCESSING LETTERS, 2005, 15 (1-2)

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

DIJKSTRA, EW .

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

[8]

Dolev S., 2000, Self-Stabilization

[9]

Dubois S., 2011, TECHNICAL REPORT

[10]

Fernau H., 2007, 33 INT C CURR TRENDS, P61

← 1 2 →