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

Chi Hung Tzeng; Jehn Ruey Jiang; Shing Tsaan Huang

doi:10.1016/j.ipl.2006.09.004

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

Chi Hung Tzeng, Jehn Ruey Jiang, Shing Tsaan Huang

Department of Computer Science and Information Engineering

Research output: Contribution to journal › Article › peer-review

11 Scopus citations

Abstract

This paper proposes a self-stabilizing edge-coloring algorithm using (Δ + 4) colors for distributed systems of a planar graph topology, where Δ ≥ 5 is the maximum degree of the graph. The algorithm can be applied to anonymous uniform systems and its time complexity is O (n²) moves under the central daemon model.

Original language	English
Pages (from-to)	168-173
Number of pages	6
Journal	Information Processing Letters
Volume	101
Issue number	4
DOIs	https://doi.org/10.1016/j.ipl.2006.09.004
State	Published - 28 Feb 2007

Keywords

Distributed systems
Edge coloring
Planar graphs
Self-stabilization

Access to Document

10.1016/j.ipl.2006.09.004

Cite this

@article{da98def4db7d4008ba8b8cdc38ad5238,

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

abstract = "This paper proposes a self-stabilizing edge-coloring algorithm using (Δ + 4) colors for distributed systems of a planar graph topology, where Δ ≥ 5 is the maximum degree of the graph. The algorithm can be applied to anonymous uniform systems and its time complexity is O (n2) moves under the central daemon model.",

keywords = "Distributed systems, Edge coloring, Planar graphs, Self-stabilization",

author = "Tzeng, {Chi Hung} and Jiang, {Jehn Ruey} and Huang, {Shing Tsaan}",

note = "Funding Information: ✩ This research was supported in part by the National Science Council of the Republic of China under the Contract NSC 94-2213-E-008-001. * Corresponding author. E-mail address: jrjiang@csie.ncu.edu.tw (J.-R. Jiang).",

year = "2007",

month = feb,

day = "28",

doi = "10.1016/j.ipl.2006.09.004",

language = "???core.languages.en_GB???",

volume = "101",

pages = "168--173",

journal = "Information Processing Letters",

issn = "0020-0190",

number = "4",

}

TY - JOUR

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

AU - Tzeng, Chi Hung

AU - Jiang, Jehn Ruey

AU - Huang, Shing Tsaan

N1 - Funding Information: ✩ This research was supported in part by the National Science Council of the Republic of China under the Contract NSC 94-2213-E-008-001. * Corresponding author. E-mail address: jrjiang@csie.ncu.edu.tw (J.-R. Jiang).

PY - 2007/2/28

Y1 - 2007/2/28

N2 - This paper proposes a self-stabilizing edge-coloring algorithm using (Δ + 4) colors for distributed systems of a planar graph topology, where Δ ≥ 5 is the maximum degree of the graph. The algorithm can be applied to anonymous uniform systems and its time complexity is O (n2) moves under the central daemon model.

AB - This paper proposes a self-stabilizing edge-coloring algorithm using (Δ + 4) colors for distributed systems of a planar graph topology, where Δ ≥ 5 is the maximum degree of the graph. The algorithm can be applied to anonymous uniform systems and its time complexity is O (n2) moves under the central daemon model.

KW - Distributed systems

KW - Edge coloring

KW - Planar graphs

KW - Self-stabilization

UR - http://www.scopus.com/inward/record.url?scp=33845380849&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2006.09.004

DO - 10.1016/j.ipl.2006.09.004

M3 - 期刊論文

AN - SCOPUS:33845380849

VL - 101

SP - 168

EP - 173

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 4

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this