Publication:
Dynamic storage allocation and on-line colouring interval graphs

Placeholder Image
Date
01-01-2004
Authors
N S Narayanaswamy
Journal Title
Journal ISSN
Volume Title
Publisher
Research Projects
Organizational Units
Journal Issue
Abstract
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.
Description
Keywords
Citation
Collections