Online Multi-Coloring with Advice
| Autor: | Christ, Marie Gabriele, Favrholdt, Lene Monrad, Larsen, Kim Skak |
|---|---|
| Přispěvatelé: | Bampis, Evripidis, Svensson, Ola |
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: | |
| Zdroj: | Christ, M G, Favrholdt, L M & Larsen, K S 2015, Online Multi-Coloring with Advice . in E Bampis & O Svensson (eds), Approximation and Online Algorithms : 12th International Workshop, WAOA 2014, Wrocław, Poland, September 11-12, 2014, Revised Selected Papers . Springer, Lecture Notes in Computer Science, vol. 8952, pp. 83-94, 12th Workshop on Approximation and Online Algorithms, Wrocław, Poland, 11/09/2014 . https://doi.org/10.1007/978-3-319-18263-6_8 |
| DOI: | 10.1007/978-3-319-18263-6_8 |
| Popis: | 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. The advice given represents information that is likely to be available, studying for instance the data from earlier similar periods of time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|