| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 436458 | Theoretical Computer Science | 2006 | 10 Pages |
Abstract
We present an improved online algorithm for coloring interval graphs with bandwidth. This problem has recently been studied by Adamy and Erlebach and a 195-competitive online strategy has been presented. We improve this by presenting a 10-competitive strategy. To achieve this result, we use variants of an optimal online coloring algorithm due to Kierstead and Trotter.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
