A Note on Online Colouring Problems in Overlap Graphs and Their Complements

Demange, M and Olsen, M 2018, 'A Note on Online Colouring Problems in Overlap Graphs and Their Complements', in M. S. Rahman et al. (ed.) Lecture Notes in Computer Science, vol 10755, Dhaka, Bangladesh, 3-5 March 2018, pp. 144-155.

Document type: Conference Paper
Collection: Conference Papers

Title A Note on Online Colouring Problems in Overlap Graphs and Their Complements
Author(s) Demange, M
Olsen, M
Year 2018
Conference name 12th International Workshop on Algorithms and Computation, Walcom 2018
Conference location Dhaka, Bangladesh
Conference dates 3-5 March 2018
Proceedings title Lecture Notes in Computer Science, vol 10755
Editor(s) M. S. Rahman et al.
Publisher Springer International Publishing
Place of publication Cham, Switzerland
Start page 144
End page 155
Total pages 12
Abstract We consider online versions of different colouring problems in interval overlap graphs, motivated by stacking problems. An instance is a system of time intervals presented in non-decreasing order of the left endpoints. We consider the usual colouring problem as well as b-bounded colouring and the same problems in the complement graph. We also consider the case where at most b intervals of the same colour can include the same element. For these versions, we obtain a logarithmic competitive ratio with respect to the maximum ratio of interval lengths. The best known ratio for the usual colouring was linear, and to our knowledge other variants have not been considered. Moreover, pre-processing allows us to deduce approximation results in the offline case. 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. This new partition problem by itself is of interest for future work.
Subjects Optimisation
Operations Research
Analysis of Algorithms and Complexity
Keyword(s) graph colouring
online optimisation
overlap graphs
stacking problems
DOI - identifier 10.1007/978-3-319-75172-6_13
Copyright notice © Springer International Publishing AG, part of Springer Nature 2018
ISBN 9783319751719
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in Thomson Reuters Web of Science Article
Altmetric details:
Access Statistics: 31 Abstract Views  -  Detailed Statistics
Created: Thu, 06 Dec 2018, 10:39:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us