A tight bound for online colouring of disk graphs

DOI10.1016/j.tcs.2007.04.025zbMath1125.68086OpenAlexW2136536722MaRDI QIDQ2382668

Evi Papaioannou, Aleksei V. Fishkin, Christos Kaklamanis, Ioannis Caragiannis

Publication date: 2 October 2007

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

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

zbMATH Keywords

online algorithmsdisk graphsGraph colouring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Limitations of current wireless link scheduling algorithms ⋮ Tight bounds for online coloring of basic graph classes ⋮ Note on coloring of double disk graphs ⋮ Tight Bounds for Online Coloring of Basic Graph Classes

Cites Work

• Unnamed Item
• Unnamed Item
• On distance constrained labeling of disk graphs
• Unit disk graphs
• Coloring inductive graphs on-line
• On coloring unit disk graphs
• The on-line first-fit algorithm for radio frequency assignment problems.
• On-line and first fit colorings of graphs
• Simple heuristics for unit disk graphs
• Mathematical Foundations of Computer Science 2004
• Independence and Coloring Problems on Intersection Graphs of Disks
• Representing graphs by disks and balls (a survey of recognition-complexity results)