 |
|
|||
| Authors: | Thomas Erlebach, Jiri Fiala |
| Group: | Theory of Communication Networks |
| Type: | Article |
| Title: | On-line coloring of geometric intersection graphs |
| Year: | 2002 |
| Month: | September |
| Pub-Key: | EF02 |
| Journal: | Computational Geometry: Theory and Applications |
| Volume: | 23 |
| Number: | 2 |
| 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] |
