Batch coloring of graphs

DOI10.1007/s00453-017-0386-1zbMath1414.05109OpenAlexW2766932952MaRDI QIDQ1755745

Kim S. Larsen, Leah Epstein, Asaf Levin, Joan. Boyar, Lene Monrad Favrholdt

Publication date: 11 January 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-017-0386-1

zbMATH Keywords

graph coloringonline algorithmsinterval graphsbatchessum coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Online algorithms; streaming algorithms (68W27)

Related Items (1)

Tight bounds for online coloring of basic graph classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• First-fit coloring on interval graphs has performance ratio at least 5
• On sum coloring and sum multi-coloring for restricted families of graphs
• A note on first-fit coloring of interval graphs
• Improved lower bounds for semi-online bin packing problems
• The ellipsoid method and its consequences in combinatorial optimization
• Precoloring extension. I: Interval graphs
• On the sum coloring problem on interval graphs
• Lower bounds for on-line graph coloring
• On chromatic sums and distributed resource allocation
• Lower bound for 3-batched bin packing
• The chromatic sum of a graph: history and recent developments
• Batched bin packing
• More on batched bin packing
• Online coloring known graphs
• Batched bin packing revisited
• On-line and first fit colorings of graphs
• Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is $\cal NP$-Complete
• Tight Bounds for Online Coloring of Basic Graph Classes

This page was built for publication: Batch coloring of graphs