Online Multi-Coloring with Advice

Marie Gabriele Christ, Lene Monrad Favrholdt, Kim Skak Larsen

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

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.
Original languageEnglish
Title of host publicationApproximation and Online Algorithms : 12th International Workshop, WAOA 2014, Wrocław, Poland, September 11-12, 2014, Revised Selected Papers
EditorsEvripidis Bampis, Ola Svensson
PublisherSpringer
Publication date2015
Pages83-94
ISBN (Print)978-3-319-18262-9
ISBN (Electronic)978-3-319-18263-6
DOIs
Publication statusPublished - 2015
Event12th Workshop on Approximation and Online Algorithms - Wrocław, Poland
Duration: 11. Sept 201412. Sept 2014

Workshop

Workshop12th Workshop on Approximation and Online Algorithms
Country/TerritoryPoland
CityWrocław
Period11/09/201412/09/2014
SeriesLecture Notes in Computer Science
Volume8952
ISSN0302-9743

Fingerprint

Dive into the research topics of 'Online Multi-Coloring with Advice'. Together they form a unique fingerprint.

Cite this