An improved algorithm for online coloring of intervals with bandwidth

DOI10.1016/J.TCS.2006.06.014zbMath1154.68562OpenAlexW1988534679MaRDI QIDQ860808

Amos Fiat, Meital Levy, N. S. Narayanaswamy, Yossi Azar

Publication date: 9 January 2007

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

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

zbMATH Keywords

graph coloringonline algorithmsinterval graphs

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

A new lower bound for the on-line coloring of intervals with bandwidth ⋮ Improved algorithms for scheduling unsplittable flows on paths ⋮ Online coloring of short intervals ⋮ Unnamed Item ⋮ Online interval coloring with packing constraints ⋮ On the max coloring problem ⋮ Complexity and online algorithms for minimum skyline coloring of intervals ⋮ Variable sized online interval coloring with bandwidth ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polynomial time approximation algorithm for dynamic storage allocation
• Coloring interval graphs with First-Fit
• On some packing problem related to dynamic storage allocation
• Computing and Combinatorics
• Approximation and Online Algorithms

This page was built for publication: An improved algorithm for online coloring of intervals with bandwidth