English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The vertex coloring problem has received a lot of attention in the context ofsynchronous round-based systems where, at each round, a process can send amessage to all its neighbors, and receive a message from each of them. Hence,this communication model is particularly suited to point-to-point communicationchannels. Several vertex coloring algorithms suited to these systems have beenproposed. They differ mainly in the number of rounds they require and thenumber of colors they use. This paper considers a broadcast/receivecommunication model in which message collisions and message conflicts can occur(a collision occurs when, during the same round, messages are sent to the sameprocess by too many neighbors; a conflict occurs when a process and one of itsneighbors broadcast during the same round). This communication model is suitedto systems where processes share communication bandwidths. More precisely,thepaper considers the case where, during a round, a process may either broadcasta message to its neighbors or receive a message from at most $m$ of them. Thiscaptures communication-related constraints or a local memory constraint statingthat, whatever the number of neighbors of a process, its local memory allows itto receive and store at most $m$ messages during each round. The paper definesfirst the corresponding generic vertex multi-coloring problem (a vertex canhave several colors). It focuses then on tree networks, for which it presents alower bound on the number of colors $K$ that are necessary (namely,$K=\lceil\frac{\Delta}{m}\rceil+1$, where $\Delta$ is the maximal degree of thecommunication graph), and an ssociated coloring algorithm, which is optimalwith respect to $K$.

Vertex Coloring with Communication and Local Memory Constraints in Synchronous Broadcast Networks