Online interval coloring with packing constraints

DOI10.1016/j.tcs.2008.05.018zbMath1153.68055OpenAlexW2079991317MaRDI QIDQ954991

Meital Levy, Leah Epstein

Publication date: 18 November 2008

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

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

zbMATH Keywords

online algorithmsbin packinginterval coloring

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• An improved algorithm for online coloring of intervals with bandwidth
• Resource constrained scheduling as generalized bin packing
• Algorithms for on-line bin-packing problems with cardinality constraints
• Coloring interval graphs with First-Fit
• The Ordered Open-End Bin-Packing Problem
• The Linearity of First-Fit Coloring of Interval Graphs
• On some packing problem related to dynamic storage allocation
• Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems
• Multidimensional Bin Packing Algorithms
• Approximation schemes for ordered vector packing problems
• Online Bin Packing with Cardinality Constraints
• Automata, Languages and Programming
• Approximation and Online Algorithms
• 25 pretty graph colouring problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item