Paper Info
Title
Vertex Coloring with Communication and Local Memory Constraints in Synchronous Broadcast Networks.
Abstract
This paper considers the broadcast/receive communication model in which message collisions and message conflicts can occur because processes share frequency bands. (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 precisely, the paper considers the case where, during a round, a process may either broadcast a message to its neighbors or receive a message from at most m of them. This captures communication-related constraints or a local memory constraint stating that, whatever the number of neighbors of a process, its local memory allows it to receive and store at most m messages during each round. The paper defines first the corresponding generic vertex multi-coloring problem (a vertex can have several colors). It focuses then on tree networks, for which it presents a lower bound on the number of colors K that are necessary (namely, K = [Delta/M] + 1, where Delta is the maximal degree of the communication graph), and an associated coloring algorithm, which is optimal with respect to K.
Year
DOI
Venue
2016
10.1007/978-3-319-53058-1_3
ALGORITHMS FOR SENSOR SYSTEMS (ALGOSENSORS 2016)
Keywords
DocType
Volume
Broadcast/receive,Bounded local memory,Collision-freedom,Distributed algorithm,Message-passing,Multi-coloring,Network traversal,Scalability,Synchronous system,Tree network,Vertex coloring
Conference
10050
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
8
3
Name
Order
Citations
PageRank
Hicham Lakhlef111216.86
Michel Raynal24078349.46
François Taïani321329.41