|
This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies.
For more information visit Aigaion.nl. |  |
Type of publication: | Article |
Entered by: | chita |
Title | A tight bound for online coloring of disk graphs |
Bibtex cite ID | RACTI-RU1-2007-44 |
Journal | Theoretical Computer Science (TCS) |
Year published | 2007 |
Volume | 384 |
Number | 2-3 |
Pages | 152-160 |
Abstract | We present an improved upper bound on the competitiveness of the online colouring algorithm First-Fit in disk graphs, which
are graphs representing overlaps of disks on the plane. We also show that this bound is best possible for deterministic online
colouring algorithms that do not use the disk representation of the input graph. We also present a related new lower bound for unit
disk graphs. |
Authors | |
Topics
| |
BibTeX | BibTeX |
RIS | RIS |
Attachments | |
Publication ID | 106 |
|
|