Randomized self-stabilization under distributed daemon for 6-coloring planar graph

Chi Hung Tzeng; Jehn Ruey Jiang; Shing Tsaan Huang; Cheng Feng Yeh

doi:10.1007/978-3-642-35452-6_6

Randomized self-stabilization under distributed daemon for 6-coloring planar graph

Chi Hung Tzeng, Jehn Ruey Jiang, Shing Tsaan Huang, Cheng Feng Yeh

Department of Computer Science and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

Abstract

Self-stabilization is a fault-tolerant mechanism that enables a distributed system to recover from transient faults. In this paper, we consider the coloring problem and propose the first self-stabilizing algorithm under the distributed daemon model to 6-color planar graphs. The algorithm is randomized, anonymous and uniform. Starting from any initial configuration, it finds a proper coloring in O(n) rounds for an n-node graph.

Original language	English
Title of host publication	Advances in Intelligent Systems and Applications -Volume 1 Proceedings of the International Computer Symposium ICS 2012 Held at Hualien,Taiwan
Editors	Jain Lakhmi, Chang Ruay-Shiung, Peng Sheng-Lung
Pages	41-48
Number of pages	8
DOIs	https://doi.org/10.1007/978-3-642-35452-6_6
State	Published - 2013

Publication series

Name	Smart Innovation, Systems and Technologies
Volume	20
ISSN (Print)	2190-3018
ISSN (Electronic)	2190-3026

Keywords

Distributed computing
Graph coloring
Planar graph
Randomization
Selfstabilization

Access to Document

10.1007/978-3-642-35452-6_6

Cite this

Tzeng, C. H., Jiang, J. R., Huang, S. T., & Yeh, C. F. (2013). Randomized self-stabilization under distributed daemon for 6-coloring planar graph. In J. Lakhmi, C. Ruay-Shiung, & P. Sheng-Lung (Eds.), Advances in Intelligent Systems and Applications -Volume 1 Proceedings of the International Computer Symposium ICS 2012 Held at Hualien,Taiwan (pp. 41-48). (Smart Innovation, Systems and Technologies; Vol. 20). https://doi.org/10.1007/978-3-642-35452-6_6

Tzeng, Chi Hung ; Jiang, Jehn Ruey ; Huang, Shing Tsaan et al. / Randomized self-stabilization under distributed daemon for 6-coloring planar graph. Advances in Intelligent Systems and Applications -Volume 1 Proceedings of the International Computer Symposium ICS 2012 Held at Hualien,Taiwan. editor / Jain Lakhmi ; Chang Ruay-Shiung ; Peng Sheng-Lung. 2013. pp. 41-48 (Smart Innovation, Systems and Technologies).

@inbook{b44de95718ad432f98fa01169d872fb2,

title = "Randomized self-stabilization under distributed daemon for 6-coloring planar graph",

abstract = "Self-stabilization is a fault-tolerant mechanism that enables a distributed system to recover from transient faults. In this paper, we consider the coloring problem and propose the first self-stabilizing algorithm under the distributed daemon model to 6-color planar graphs. The algorithm is randomized, anonymous and uniform. Starting from any initial configuration, it finds a proper coloring in O(n) rounds for an n-node graph.",

keywords = "Distributed computing, Graph coloring, Planar graph, Randomization, Selfstabilization",

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

year = "2013",

doi = "10.1007/978-3-642-35452-6_6",

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

isbn = "9783642354519",

series = "Smart Innovation, Systems and Technologies",

pages = "41--48",

editor = "Jain Lakhmi and Chang Ruay-Shiung and Peng Sheng-Lung",

booktitle = "Advances in Intelligent Systems and Applications -Volume 1 Proceedings of the International Computer Symposium ICS 2012 Held at Hualien,Taiwan",

}

Tzeng, CH, Jiang, JR, Huang, ST & Yeh, CF 2013, Randomized self-stabilization under distributed daemon for 6-coloring planar graph. in J Lakhmi, C Ruay-Shiung & P Sheng-Lung (eds), Advances in Intelligent Systems and Applications -Volume 1 Proceedings of the International Computer Symposium ICS 2012 Held at Hualien,Taiwan. Smart Innovation, Systems and Technologies, vol. 20, pp. 41-48. https://doi.org/10.1007/978-3-642-35452-6_6

Randomized self-stabilization under distributed daemon for 6-coloring planar graph. / Tzeng, Chi Hung; Jiang, Jehn Ruey; Huang, Shing Tsaan et al.
Advances in Intelligent Systems and Applications -Volume 1 Proceedings of the International Computer Symposium ICS 2012 Held at Hualien,Taiwan. ed. / Jain Lakhmi; Chang Ruay-Shiung; Peng Sheng-Lung. 2013. p. 41-48 (Smart Innovation, Systems and Technologies; Vol. 20).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

TY - CHAP

T1 - Randomized self-stabilization under distributed daemon for 6-coloring planar graph

AU - Tzeng, Chi Hung

AU - Jiang, Jehn Ruey

AU - Huang, Shing Tsaan

AU - Yeh, Cheng Feng

PY - 2013

Y1 - 2013

N2 - Self-stabilization is a fault-tolerant mechanism that enables a distributed system to recover from transient faults. In this paper, we consider the coloring problem and propose the first self-stabilizing algorithm under the distributed daemon model to 6-color planar graphs. The algorithm is randomized, anonymous and uniform. Starting from any initial configuration, it finds a proper coloring in O(n) rounds for an n-node graph.

AB - Self-stabilization is a fault-tolerant mechanism that enables a distributed system to recover from transient faults. In this paper, we consider the coloring problem and propose the first self-stabilizing algorithm under the distributed daemon model to 6-color planar graphs. The algorithm is randomized, anonymous and uniform. Starting from any initial configuration, it finds a proper coloring in O(n) rounds for an n-node graph.

KW - Distributed computing

KW - Graph coloring

KW - Planar graph

KW - Randomization

KW - Selfstabilization

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

U2 - 10.1007/978-3-642-35452-6_6

DO - 10.1007/978-3-642-35452-6_6

M3 - 篇章

AN - SCOPUS:84879307456

SN - 9783642354519

T3 - Smart Innovation, Systems and Technologies

SP - 41

EP - 48

BT - Advances in Intelligent Systems and Applications -Volume 1 Proceedings of the International Computer Symposium ICS 2012 Held at Hualien,Taiwan

A2 - Lakhmi, Jain

A2 - Ruay-Shiung, Chang

A2 - Sheng-Lung, Peng

ER -

Tzeng CH, Jiang JR, Huang ST, Yeh CF. Randomized self-stabilization under distributed daemon for 6-coloring planar graph. In Lakhmi J, Ruay-Shiung C, Sheng-Lung P, editors, Advances in Intelligent Systems and Applications -Volume 1 Proceedings of the International Computer Symposium ICS 2012 Held at Hualien,Taiwan. 2013. p. 41-48. (Smart Innovation, Systems and Technologies). doi: 10.1007/978-3-642-35452-6_6

Randomized self-stabilization under distributed daemon for 6-coloring planar graph

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this