 |
|
|||
| Authors: | Thomas Erlebach, Jiri Fiala |
| Group: | Theory of Communication Networks |
| Type: | Techreport |
| Title: | On-line Coloring of Geometric Intersection Graphs |
| Year: | 2002 |
| Month: | February |
| Pub-Key: | EF02tr |
| Number: | 552 |
| Institution: | Institute for Theoretical Computer Science (ITI), Charles University |
| Abstract: | This paper studies on-line coloring of geometric intersection graphs. It is shown that no deterministic on-line algorithm can achieve competitive ratio better than Omega(log n) for disk graphs and for square graphs with n vertices, even if the geometric representation is given as part of the input. Furthermore, it is proved that the standard First-fit heuristic achieves competitive ratio O(log n) for disk graphs and for square graphs and is thus best possible. |
| Resources: | [BibTeX] |
