Aigaion: RACTI / RU1 Technical Report Series (Web Based)

[RACTI-RU1-2007-44] Caragiannis, Ioannis, Fishkin, A, Kaklamanis, Christos and Papaioannou, Evi, A tight bound for online coloring of disk graphs, in: Theoretical Computer Science (TCS), volume 384, number 2-3, pages 152-160, 2007.
[RACTI-RU1-2004-44] Caragiannis, Ioannis, Fishkin, A, Kaklamanis, Christos and Papaioannou, Evi, On-line algorithms for disk graphs, in: 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004), pages 215-226, Springer, 2004.
[RACTI-RU1-2007-46] Caragiannis, Ioannis, Fishkin, A, Kaklamanis, Christos and Papaioannou, Evi, Randomized Online Algorithms and Lower Bounds for Computing Large Independent Sets in Disk Graphs, in: Discrete Applied Mathematics, volume 155, number 2, pages 119-136, 2007.
[RACTI-RU1-2005-60] Caragiannis, Ioannis, Fishkin, A, Kaklamanis, Christos and Papaioannou, Evi, Tight bounds for online coloring of disk graphs, in: 12th Colloquium on Structural Information and Communication Complexity (SIROCCO 2005), pages 78-88, Springer, 2005. [DOI]

[RACTI-RU1-2007-46] Caragiannis, Ioannis, Fishkin, A, Kaklamanis, Christos and Papaioannou, Evi, Randomized Online Algorithms and Lower Bounds for Computing Large Independent Sets in Disk Graphs, in: Discrete Applied Mathematics, volume 155, number 2, pages 119-136, 2007.

Keywords:

On-line algorithms; Competitive analysis; Maximum independent set; Disk graphs

[RACTI-RU1-2005-60] Caragiannis, Ioannis, Fishkin, A, Kaklamanis, Christos and Papaioannou, Evi, Tight bounds for online coloring of disk graphs, in: 12th Colloquium on Structural Information and Communication Complexity (SIROCCO 2005), pages 78-88, Springer, 2005. [DOI]

Keywords:

Graph colouring; Online algorithms; Disk graphs

[RACTI-RU1-2007-44] Caragiannis, Ioannis, Fishkin, A, Kaklamanis, Christos and Papaioannou, Evi, A tight bound for online coloring of disk graphs, in: Theoretical Computer Science (TCS), volume 384, number 2-3, pages 152-160, 2007.
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.
[RACTI-RU1-2004-44] Caragiannis, Ioannis, Fishkin, A, Kaklamanis, Christos and Papaioannou, Evi, On-line algorithms for disk graphs, in: 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004), pages 215-226, Springer, 2004.
Abstract: We study the on-line versions of two fundamental graph problems, maximum independent set and minimum coloring, for the case of disk graphs which are graphs resulting from intersections of disks on the plane. In particular, we investigate whether randomization can be used to break known lower bounds for deterministic on-line independent set algorithms and present new upper and lower bounds; we also present an improved upper bound for on-line coloring.
[RACTI-RU1-2007-46] Caragiannis, Ioannis, Fishkin, A, Kaklamanis, Christos and Papaioannou, Evi, Randomized Online Algorithms and Lower Bounds for Computing Large Independent Sets in Disk Graphs, in: Discrete Applied Mathematics, volume 155, number 2, pages 119-136, 2007.
Abstract: We study the on-line version of the maximum independent set problem, for the case of disk graphs which are graphs resulting from intersections of disks on the plane. In particular, we investigate whether randomization can be used to break known lower bounds for deterministic on-line independent set algorithms and present new upper and lower bounds.
[RACTI-RU1-2005-60] Caragiannis, Ioannis, Fishkin, A, Kaklamanis, Christos and Papaioannou, Evi, Tight bounds for online coloring of disk graphs, in: 12th Colloquium on Structural Information and Communication Complexity (SIROCCO 2005), pages 78-88, Springer, 2005. [DOI]
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.