TY - CHAP
T1 - Edge coloring with delays
AU - Alon, Noga
AU - Asodi, Vera
PY - 2004
Y1 - 2004
N2 - Consider the following communication problem, that leads to a new notion of edge coloring. The communication network is represented by a bipartite multigraph, where the nodes on one side are the transmitters and the nodes on the other side are the receivers. The edges correspond to messages, and every edge e is associated with an integer c(e), corresponding to the time it takes the message to reach its destination. A proper k-edge-coloring with delays is a function f from the edges to {0,1,..., k-1), such that for every two edges e1 and e2 with the same transmitter, f(e1) ≠ f(e2), and for every two edges e1 and e2 with the same receiver, f(e1)+c(e1) ≢ f(e2) + c(e2) (mod k). Haxell, Wilfong and Winkler [10] conjectured that there always exists a proper edge coloring with delays using k = Δ + 1 colors, where Δ is the maximum degree of the graph. We prove that the conjecture asymptotically holds for simple bipartite graphs, using a probabilistic approach, and further show that it holds for some multigraphs, applying algebraic tools. The probabilistic proof provides an efficient algorithm for the corresponding algorithmic problem, whereas the algebraic method does not.
AB - Consider the following communication problem, that leads to a new notion of edge coloring. The communication network is represented by a bipartite multigraph, where the nodes on one side are the transmitters and the nodes on the other side are the receivers. The edges correspond to messages, and every edge e is associated with an integer c(e), corresponding to the time it takes the message to reach its destination. A proper k-edge-coloring with delays is a function f from the edges to {0,1,..., k-1), such that for every two edges e1 and e2 with the same transmitter, f(e1) ≠ f(e2), and for every two edges e1 and e2 with the same receiver, f(e1)+c(e1) ≢ f(e2) + c(e2) (mod k). Haxell, Wilfong and Winkler [10] conjectured that there always exists a proper edge coloring with delays using k = Δ + 1 colors, where Δ is the maximum degree of the graph. We prove that the conjecture asymptotically holds for simple bipartite graphs, using a probabilistic approach, and further show that it holds for some multigraphs, applying algebraic tools. The probabilistic proof provides an efficient algorithm for the corresponding algorithmic problem, whereas the algebraic method does not.
UR - http://www.scopus.com/inward/record.url?scp=35048888981&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35048888981&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-27821-4_22
DO - 10.1007/978-3-540-27821-4_22
M3 - Chapter
AN - SCOPUS:35048888981
SN - 3540228942
SN - 9783540228943
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 237
EP - 248
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - Jansen, Klaus
A2 - Khanna, Sanjeev
A2 - Rolim, Jose D. P.
A2 - Ron, Dana
PB - Springer Verlag
ER -