Skip to Main content Skip to Navigation
Journal articles

Vertex Coloring with Communication Constraints in Synchronous Broadcast Networks

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; presents a deterministic, parallel, color-optimal, collision-and conflict-free distributed coloring algorithm for trees; proves the correctness of this algorithm; and finally evaluates experimentally its performance using simulations that show our solution clearly outperforms a reference protocol for distributed TDMA slot-allocation.
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : François Taïani Connect in order to contact the contributor
Submitted on : Friday, November 22, 2019 - 5:07:23 PM
Last modification on : Tuesday, October 19, 2021 - 11:04:42 AM


Files produced by the author(s)




Hicham Lakhlef, Michel Raynal, François Taïani. Vertex Coloring with Communication Constraints in Synchronous Broadcast Networks. IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 2019, 30 (7), pp.1672-1686. ⟨10.1109/TPDS.2018.2889688⟩. ⟨hal-02376726⟩



Record views


Files downloads