Generalised online colouring problems in overlap graphs

DOI10.1016/J.TCS.2021.05.004MaRDI QIDQ2034796zbMATH OpenOpenAlexFDO

Authors 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 algorithmscompetitive preserving reductiononline colouringoverlap graphspermutation graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• A note on online colouring problems in overlap graphs and their complements
• Online Bounded Coloring of Permutation and Overlap Graphs
• Online coloring co-interval graphs
• Max-coloring and online coloring with bandwidths on interval graphs

Cites work

• A note on online colouring problems in overlap graphs and their complements
• Algorithmic graph theory and perfect graphs
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• Coloring circle graphs
• Container ship stowage problem complexity and connection to the coloring of circle graphs
• Efficient algorithms for interval graphs and circular-arc graphs
• scientific article; zbMATH DE number 4051024 (Why is no real title available?)
• scientific article; zbMATH DE number 3611388 (Why is no real title available?)
• On split-coloring problems
• On the independence number of random interval graphs
• On the online track assignment problem
• On the performance of the first-fit coloring algorithm on permutation graphs
• Sorting with Complete Networks of Stacks
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• Track assignment

Cited in

(3)

• A note on online colouring problems in overlap graphs and their complements
• In memory of Jérôme Monnot
• Online Bounded Coloring of Permutation and Overlap Graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2034796)