Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Caragiannis, Ioannis
Fishkin, Aleksei V.
Kaklamanis, Christos
Papaioannou, Evi

dblp
dblp
dblp
dblp

Not MPG Author(s):

Caragiannis, Ioannis
Kaklamanis, Christos
Papaioannou, Evi

BibTeX cite key*:

Caragioannis2007

Title

Title*:

A tight bound for online colouring of disk graphs

Journal

Journal Title*:

Theoretical Computer Science

Journal's URL:

http://www.elsevier.com/wps/find/journaldescription.cws_home/505625/description#description

Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:


Publisher's
Address:

Amsterdam, The Netherlands

ISSN:

0304-3975

Vol, No, pp, Date

Volume*:

384

Number:

2/3

Publishing Date:

October 2007

Pages*:

152-160

Number of
VG Pages:


Page Start:

152

Page End:

160

Sequence Number:


DOI:

10.1016/j.tcs.2007.04.025

Note, Abstract, ©

Note:


(LaTeX) 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

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{Caragioannis2007,
AUTHOR = {Caragiannis, Ioannis and Fishkin, Aleksei V. and Kaklamanis, Christos and Papaioannou, Evi},
TITLE = {A tight bound for online colouring of disk graphs},
JOURNAL = {Theoretical Computer Science},
PUBLISHER = {Elsevier},
YEAR = {2007},
NUMBER = {2/3},
VOLUME = {384},
PAGES = {152--160},
ADDRESS = {Amsterdam, The Netherlands},
MONTH = {October},
ISBN = {0304-3975},
DOI = {10.1016/j.tcs.2007.04.025},
}


Entry last modified by Anja Becker, 02/28/2008
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Anja Becker
Created
02/07/2008 03:00:39 PM
Revision
1.
0.


Editor
Anja Becker
Anja Becker


Edit Date
22.02.2008 11:17:35
07.02.2008 15:06:44