Batch Coloring of Graphs
From MaRDI portal
Publication:2971156
DOI10.1007/978-3-319-51741-4_5zbMath1484.05062arXiv1610.02997OpenAlexW2530763722MaRDI QIDQ2971156
Leah Epstein, Kim S. Larsen, Asaf Levin, Lene Monrad Favrholdt, Joan. Boyar
Publication date: 4 April 2017
Published in: Approximation and Online Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1610.02997
Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)
Related Items
Cites Work
- 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
- 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
- Batch Coloring of Graphs
- On-line and first fit colorings of graphs
