Vertex Coloring with Communication Constraints in Synchronous Broadcast Networks

Hicham Lakhlef, Michel Raynal, François Taı̈aniIEEE TPDS 2018 · DOI

Abstract

This paper considers distributed vertex-coloring in broadcast/receive networks suffering from conflicts and collisions. (A collision occurs when, during the same round, messages are sent to the same process by too many neighbors; a conflict occurs when a process and one of its neighbors broadcast during the same round.) More specifically, the paper focuses on multi-channel networks, in which a process may either broadcast a message to its neighbors or receive a message from at most γ of them. The paper first provides a new upper bound on the corresponding graph coloring problem (known as frugal coloring) in general graphs, proposes an exact bound for the problem in trees, and presents a deterministic, parallel, color-optimal, collision- and conflict-free distributed coloring algorithm for trees, and proves its correctness.
BibTeX
@article{lakhlef2018vertex,
  author = {Hicham Lakhlef and Michel Raynal and François Taı̈ani},
  title = {{Vertex Coloring with Communication Constraints in Synchronous Broadcast Networks}},
  journal = {IEEE Transactions on Parallel and Distributed Systems},
  year = {2018},
  doi = {10.1109/tpds.2018.2889688},
}
Figure