Online coloring of short intervals

DOI10.1016/J.EJC.2024.103919MaRDI QIDQ6201896zbMATH OpenOpenAlexWikidataFDO

Authors

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

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

Recommendations

• Online coloring co-interval graphs
• Coloring interval graphs with First-Fit
• scientific article; zbMATH DE number 820116
• First-fit coloring on interval graphs has performance ratio at least 5
• scientific article; zbMATH DE number 17824

Cites work

• scientific article; zbMATH DE number 3769624 (Why is no real title available?)
• scientific article; zbMATH DE number 17824 (Why is no real title available?)
• scientific article; zbMATH DE number 7758354 (Why is no real title available?)
• A note on first-fit coloring of interval graphs
• Algorithmic graph theory and perfect graphs
• An improved algorithm for online coloring of intervals with bandwidth
• An on-line competitive algorithm for coloring bipartite graphs without long induced paths
• An on-line graph coloring algorithm with sublinear performance ratio
• Automata, Languages and Programming
• Classes of interval graphs under expanding length restrictions
• Effective coloration
• First-fit coloring on interval graphs has performance ratio at least 5
• Lower bounds for on-line graph coloring
• Lower bounds for on-line graph colorings
• On some packing problem related to dynamic storage allocation
• On-line and first fit colorings of graphs
• On-line approach to off-line coloring problems on graphs with geometric representations
• On-line coloring of geometric intersection graphs
• Online coloring and \(L(2,1)\)-labeling of unit disk intersection graphs
• Parallel and On-Line Graph Coloring
• Representation of a finite graph by a set of intervals on the real line
• Tight bounds for online coloring of basic graph classes

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

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