| Type of publication: | Inproceedings |
| Entered by: | |
| Title | Tight bounds for online coloring of disk graphs |
| Bibtex cite ID | RACTI-RU1-2005-60 |
| Booktitle | 12th Colloquium on Structural Information and Communication Complexity (SIROCCO 2005) |
| Year published | 2005 |
| Volume | LNCS |
| Number | 3499 |
| Pages | 78-88 |
| Publisher | Springer |
| URL | http://www.ceid.upatras.gr/papaioan/sirocco05.pdf |
| DOI | 10.1016/j.tcs.2007.04.025 |
| Keywords | Graph colouring; Online algorithms; Disk graphs |
| 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 | 537 |
