We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A Self-Stabilizing Distance-2 Edge Coloring Algorithm.
- Authors
Lee, Chia-Lin; Liu, Tzong-Jye
- Abstract
In this paper, we propose a self-stabilizing distance-2 edge coloring algorithm for arbitrary graphs. The algorithm operates correctly under the distributed model and guarantees that two edges within distance 2 of each other receive distinct colors when the system stabilizes. It uses 2Δ (Δ − 1) + 1 colors and stabilizes in 4n + (2Δ (Δ − 1) + 2)m rounds, where n, m, respectively, denote the number of nodes and edges and Δ is the maximum degree of nodes in the graph.
- Subjects
GRAPH coloring; COMPUTER algorithms; WIRELESS communications; BIPARTITE graphs; PLANAR graphs
- Publication
Computer Journal, 2014, Vol 57, Issue 11, p1639
- ISSN
0010-4620
- Publication type
Article
- DOI
10.1093/comjnl/bxt072