A self-stabilizing (Δ+4)-edge-coloring algorithm for planar graphs in anonymous uniform systems

被引：10

作者：

Tzeng, Chi-Hung ^{[1
]}

Jiang, Jehn-Ruey ^{[1
]}

Huang, Shing-Tsaan ^{[1
]}

机构：

[1] Natl Cent Univ, Dept Comp Sci & Informat Engn, Taipei, Taiwan

来源：

INFORMATION PROCESSING LETTERS | 2007年 / 101卷 / 04期

关键词：

distributed systems; edge coloring; planar graphs; self-stabilization;

D O I：

10.1016/j.ipl.2006.09.004

中图分类号：

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

学科分类号：

0812 ;

摘要：

This paper proposes a self-stabilizing edge-coloring algorithm using (Delta + 4) colors for distributed systems of a planar graph topology, where Delta >= 5 is the maximum degree of the graph. The algorithm can be applied to anonymous uniform systems and its time complexity is O(n(2)) moves under the central daemon model. (c) 2006 Elsevier B.V. All rights reserved.

引用

页码：168 / 173

页数：6

共 17 条

[1] COLORING PLANAR GRAPHS IN PARALLEL [J].

BOYAR, JF ;

KARLOFF, HJ .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1987, 8 (04) :470-479

[2] Self-stabilizing algorithms for finding centers and medians of trees [J].

Bruell, SC ;

Ghosh, S ;

Karaata, MH ;

Pemmaraju, SV .

SIAM JOURNAL ON COMPUTING, 1999, 29 (02) :600-614

[3] IMPROVED EDGE-COLORING ALGORITHMS FOR PLANAR GRAPHS [J].

CHROBAK, M ;

NISHIZEKI, T .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1990, 11 (01) :102-116

[4] Edge-coloring bipartite multigraphs in O(ElogD) time [J].

Cole, R ;

Ost, K ;

Schirra, S .

COMBINATORICA, 2001, 21 (01) :5-12

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

DIJKSTRA, EW .

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

[6] ALGORITHMS FOR EDGE COLORING BIPARTITE GRAPHS AND MULTIGRAPHS [J].

GABOW, HN ;

KARIV, O .

SIAM JOURNAL ON COMPUTING, 1982, 11 (01) :117-129

[7] A SELF-STABILIZING ALGORITHM FOR COLORING PLANAR GRAPHS [J].

GHOSH, S ;

KARAATA, MH .

DISTRIBUTED COMPUTING, 1993, 7 (01) :55-59

[8]

Grable DA, 1997, RANDOM STRUCT ALGOR, V10, P385, DOI 10.1002/(SICI)1098-2418(199705)10:3<385::AID-RSA6>3.0.CO

[9]

2-S

[10] THE NP-COMPLETENESS OF EDGE-COLORING [J].

HOLYER, I .

SIAM JOURNAL ON COMPUTING, 1981, 10 (04) :718-720

← 1 2 →