Generalised online colouring problems in overlap graphs

DOI10.1016/j.tcs.2021.05.004OpenAlexW3163872508MaRDI QIDQ2034796

Marc Demange, Martin Olsen

Publication date: 23 June 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2021.05.004

zbMATH Keywords

approximation algorithmspermutation graphsoverlap graphsonline colouringcompetitive preserving reduction

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

In memory of Jérôme Monnot

Cites Work

• Unnamed Item
• Unnamed Item
• On the performance of the first-fit coloring algorithm on permutation graphs
• On the online track assignment problem
• On split-coloring problems
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• Container ship stowage problem complexity and connection to the coloring of circle graphs
• A note on online colouring problems in overlap graphs and their complements
• Algorithmic graph theory and perfect graphs
• Track assignment
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• On the Independence Number of Random Interval Graphs
• Coloring circle graphs
• Sorting with Complete Networks of Stacks
• Efficient algorithms for interval graphs and circular-arc graphs
• Algorithms for a maximum clique and a maximum independent set of a circle graph

This page was built for publication: Generalised online colouring problems in overlap graphs