TY - JOUR
T1 - Online Multi-Coloring with Advice
AU - Christ, Marie Gabriele
AU - Favrholdt, Lene Monrad
AU - Larsen, Kim Skak
PY - 2015
Y1 - 2015
N2 - We consider the problem of online graph multi-coloring with advice. Multi-coloring is often used to model frequency allocation in cellular networks. We give several nearly tight upper and lower bounds for the most standard topologies of cellular networks, paths and hexagonal graphs. For the path, negative results trivially carry over to bipartite graphs, and our positive results are also valid for bipartite graphs. For hexagonal graphs, negative results trivially carry over to 3-colorable graphs, and most of our positive results do as well. The advice given represents information that is likely to be available, studying for instance the data from earlier similar periods of time.
AB - We consider the problem of online graph multi-coloring with advice. Multi-coloring is often used to model frequency allocation in cellular networks. We give several nearly tight upper and lower bounds for the most standard topologies of cellular networks, paths and hexagonal graphs. For the path, negative results trivially carry over to bipartite graphs, and our positive results are also valid for bipartite graphs. For hexagonal graphs, negative results trivially carry over to 3-colorable graphs, and most of our positive results do as well. The advice given represents information that is likely to be available, studying for instance the data from earlier similar periods of time.
U2 - 10.1016/j.tcs.2015.06.044
DO - 10.1016/j.tcs.2015.06.044
M3 - Journal article
SN - 0304-3975
VL - 596
SP - 79
EP - 91
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -