Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler

被引：51

作者：

Turau, Volker ^{[1
]}

机构：

[1] Hamburg Univ Technol, Inst Telematics, D-21073 Hamburg, Germany

来源：

INFORMATION PROCESSING LETTERS | 2007年 / 103卷 / 03期

关键词：

self-stabilizing algorithms; fault tolerance; distributed computing; graph algorithms;

D O I：

10.1016/j.ipl.2007.02.013

中图分类号：

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

学科分类号：

0812 ;

摘要：

This paper presents distributed self-stabilizing algorithms for the maximal independent and the minimal dominating set problems. Using an unfair distributed scheduler the algorithms stabilizes in at most max{3n - 5, 2n} resp. 9n moves. All previously known algorithms required O(n(2)) moves. (c) 2007 Elsevier B.V. All rights reserved.

引用

页码：88 / 93

页数：6

共 10 条

[1]

Alzoubi K. M., 2003, International Journal of Foundations of Computer Science, V14, P287, DOI 10.1142/S012905410300173X

[2]

BEAUQUIER J, 2002, CHICAGO J THEORETICA, V1

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

DIJKSTRA, EW .

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

[4]

Dolev S., 2000, Self-Stabilization

[5]

GODDARD W, 2003, P INT PAR DISTR PROC

[6]

Hedetniemi SM, 2003, COMPUT MATH APPL, V46, P805, DOI 10.1016/S0898-1221(03)00286-4

[7]

Ikeda Michiyo, 2002, P 3 INT C PAR DISTR, P70

[8]

SHUKLA S, 1995, P 2 WORKSH SELF STAB

[9]

Turau V, 2006, LECT NOTES COMPUT SC, V4124, P74

[10]

Xu Z, 2003, LECT NOTES COMPUT SC, V2918, P26

← 1 →