Online coloring of short intervals

DOI10.1016/j.ejc.2024.103919OpenAlexW2788939977WikidataQ129827014 ScholiaQ129827014MaRDI QIDQ6201896

No author found.

Publication date: 26 March 2024

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2024.103919

zbMATH Keywords

\((1+\sigma)\)-competitive algorithmFirstFit algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• First-fit coloring on interval graphs has performance ratio at least 5
• An on-line competitive algorithm for coloring bipartite graphs without long induced paths
• On-line approach to off-line coloring problems on graphs with geometric representations
• An improved algorithm for online coloring of intervals with bandwidth
• A note on first-fit coloring of interval graphs
• An on-line graph coloring algorithm with sublinear performance ratio
• Lower bounds for on-line graph coloring
• On-line coloring of geometric intersection graphs
• Algorithmic graph theory and perfect graphs
• Tight bounds for online coloring of basic graph classes
• Lower Bounds for On-line Graph Colorings
• Representation of a finite graph by a set of intervals on the real line
• On-line and first fit colorings of graphs
• Classes of interval graphs under expanding length restrictions
• On some packing problem related to dynamic storage allocation
• Effective coloration
• Parallel and On-Line Graph Coloring
• Online Coloring and $L(2,1)$-Labeling of Unit Disk Intersection Graphs
• Automata, Languages and Programming

This page was built for publication: Online coloring of short intervals