Department of Business Development and Technology

Generalised online colouring problems in overlap graphs

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Marc Demange, Royal Melbourne Institute of Technology University
  • ,
  • Martin Olsen

In this paper we consider an online version of different colouring problems in overlap graphs, motivated by some stacking problems. The instance is a system of time intervals presented in non-decreasing order of the left endpoint. We consider the usual colouring problem as well as b-bounded colouring (colour class have a maximum capacity b) and the same problems in the complement graph. We also consider the case where at most b intervals of the same colour can intersect. For all these versions we obtain a logarithmic competitive ratio w.r.t. the maximum ratio of interval lengths while the best known ratio for the usual colouring was linear. To our knowledge it is the first time the other variants are considered in online overlap graphs. Moreover, in the offline case, a pre-processing allows us to deduce a logarithmic approximation ratio w.r.t. the maximum number of pairwise disjoint intervals in the system. Our method is based on a partition of the overlap graph into permutation graphs, leading to a competitive-preserving reduction of the problem in overlap graphs to the same problem in permutation graphs. We think that this new partition problem by itself is of interest for future work.

Original languageEnglish
JournalTheoretical Computer Science
Volume877
Pages (from-to)58-73
Number of pages16
ISSN0304-3975
DOIs
Publication statusPublished - Jul 2021

Bibliographical note

Publisher Copyright:
© 2021 Elsevier B.V.

    Research areas

  • Approximation algorithms, Competitive preserving reduction, Online colouring, Overlap graphs, Permutation graphs

See relations at Aarhus University Citationformats

ID: 220077984