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

Standard

Generalised online colouring problems in overlap graphs. / Demange, Marc; Olsen, Martin.

In: Theoretical Computer Science, Vol. 877, 07.2021, p. 58-73.

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

Harvard

Demange, M & Olsen, M 2021, 'Generalised online colouring problems in overlap graphs', Theoretical Computer Science, vol. 877, pp. 58-73. https://doi.org/10.1016/j.tcs.2021.05.004

APA

CBE

MLA

Vancouver

Author

Demange, Marc ; Olsen, Martin. / Generalised online colouring problems in overlap graphs. In: Theoretical Computer Science. 2021 ; Vol. 877. pp. 58-73.

Bibtex

@article{199b41f9cbe547c996995cd4b801b604,
title = "Generalised online colouring problems in overlap graphs",
abstract = "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.",
keywords = "Approximation algorithms, Competitive preserving reduction, Online colouring, Overlap graphs, Permutation graphs",
author = "Marc Demange and Martin Olsen",
note = "Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",
year = "2021",
month = jul,
doi = "10.1016/j.tcs.2021.05.004",
language = "English",
volume = "877",
pages = "58--73",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier BV",

}

RIS

TY - JOUR

T1 - Generalised online colouring problems in overlap graphs

AU - Demange, Marc

AU - Olsen, Martin

N1 - Publisher Copyright: © 2021 Elsevier B.V.

PY - 2021/7

Y1 - 2021/7

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Competitive preserving reduction

KW - Online colouring

KW - Overlap graphs

KW - Permutation graphs

UR - http://www.scopus.com/inward/record.url?scp=85106521396&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2021.05.004

DO - 10.1016/j.tcs.2021.05.004

M3 - Journal article

AN - SCOPUS:85106521396

VL - 877

SP - 58

EP - 73

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -