RECORD
Vertex Coloring with Communication and Local Memory Constraints in Synchronous Broadcast Networks
Distributed, Parallel, and Cluster Computing · Submitted 12 Apr 2016
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim It focuses then on tree networks, for which it presents a lower 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 the communication graph), and an ssociated coloring algorithm, which is optimal with respect to $K$.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
The vertex coloring problem has received a lot of attention in the context of synchronous round-based systems where, at each round, a process can send a message to all its neighbors, and receive a message from each of them. Hence, this communication model is particularly suited to point-to-point communication channels. Several vertex coloring algorithms suited to these systems have been proposed. They differ mainly in the number of rounds they require and the number of colors they use. This paper considers a broadcast/receive communication model in which message collisions and message conflicts can occur (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). This communication model is suited to systems where processes share communication bandwidths. 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=\lceil\frac{\Delta}{m}\rceil+1$, where $\Delta$ is the maximal degree of the communication graph), and an ssociated coloring algorithm, which is optimal with respect to $K$.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | The vertex coloring problem has received a lot of attention in the context of synchronous round-based systems where, at each round, a process can send a message to all its neighbors, and receive a message from each of them. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s1 | Hence, this communication model is particularly suited to point-to-point communication channels. | background 0.86 | 0.07 | 0.02 | asserted 0.96 |
| s2 | Several vertex coloring algorithms suited to these systems have been proposed. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s3 | They differ mainly in the number of rounds they require and the number of colors they use. | background 1.00 | 0.05 | 0.02 | asserted 1.00 |
| s4 | This paper considers a broadcast/receive communication model in which message collisions and message conflicts can occur (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). | contribution 0.51 | 0.26 | 0.03 | asserted 0.99 |
| s5 | This communication model is suited to systems where processes share communication bandwidths. | background 0.62 | 0.14 | 0.02 | asserted 0.96 |
| s6 | 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. | method 0.77 | 0.46 | 0.04 | hedged possibility 0.68 |
| s7 | 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. | method 0.42 | 0.37 | 0.04 | asserted 0.79 |
| s8 | The paper defines first the corresponding generic vertex multi-coloring problem (a vertex can have several colors). | contribution 0.77 | 0.91 | 0.04 | asserted 0.99 |
| s9 | It focuses then on tree networks, for which it presents a lower 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 the communication graph), and an ssociated coloring algorithm, which is optimal with respect to $K$. | result 0.59 | 0.95 | 0.78 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
The vertex coloring problem has received a lot of attention in the context of synchronous round-based systems where, at each round, a process can send a message to all its neighbors, and receive a message from each of them. Hence, this communication model is particularly suited to point-to-point communication channels. Several vertex coloring algorithms suited to these systems have been proposed. They differ mainly in the number of rounds they require and the number of colors they use. This paper considers a broadcast/receive communication model in which message collisions and message conflicts can occur (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). This communication model is suited to systems where processes share communication bandwidths. 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=\lceil\frac{\Delta}{m}\rceil+1$, where $\Delta$ is the maximal degree of the communication graph), and an ssociated coloring algorithm, which is optimal with respect to $K$.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.