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

Chi Hung Tzeng, Jehn Ruey Jiang, Shing Tsaan Huang

Research output: Contribution to journalArticlepeer-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 (n2) moves under the central daemon model.

Original languageEnglish
Pages (from-to)168-173
Number of pages6
JournalInformation Processing Letters
Volume101
Issue number4
DOIs
StatePublished - 28 Feb 2007

Keywords

  • Distributed systems
  • Edge coloring
  • Planar graphs
  • Self-stabilization

Fingerprint

Dive into the research topics of 'A self-stabilizing (Δ + 4)-edge-coloring algorithm for planar graphs in anonymous uniform systems'. Together they form a unique fingerprint.

Cite this