research unit 1
 

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit Aigaion.nl.SourceForge.hetLogo

Publication

Type of publication:Article
Entered by:chita
TitleA tight bound for online coloring of disk graphs
Bibtex cite IDRACTI-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
Caragiannis, Ioannis
Fishkin, A
Kaklamanis, Christos
Papaioannou, Evi
Topics
Top
BibTeXBibTeX
RISRIS
Attachments
tcs2007.pdf (main file)
 
Publication ID106