Dynamic storage allocation and on-line colouring interval graphs

We present an improved on-line algorithm for colouring interval graphs with bandwidth. This problem has recently been studied in [1] and a 195-competitive online strategy has been presented. We improve this by presenting a 10-competitive strategy. To achieve this result, we use the online colouring algorithm presented in [8, 9]. We also present a new analysis of a polynomial time 3-approximation algorithm for Dynamic Storage Allocation(DSA) using features of the optimal on-line algorithm for colouring interval graphs [8, 9]. © Springer-Verlag Berlin Heidelberg 2004.