Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

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

Action:

login to update

Options:








Author, Editor

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

Editor(s):

Kratochvíl, Jan
Díaz, Josep
Fiala , Jiří

dblp
dblp
dblp

Not MPII Editor(s):

Kratochvíl, Jan
Díaz, Josep
Fiala , Jiří

BibTeX cite key*:

CaragiannisFishkin2007

Title, Booktitle

Title*:

Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs

Booktitle*:

29th Symposium on Mathematical Foundations of Computer Science MFCS 2004

Event, URLs

URL of the conference:


URL for downloading the paper:


Event Address*:

Prague, Czech Republic

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

22 August 2004

Event End Date:

27 August 2004

Publisher

Name*:

Elsevier

URL:


Address*:

Amsterdam, The Netherlands

Type:


Vol, No, Year, pp.

Series:

Discrete Applied Mathematics

Volume:

155

Number:

2

Month:

January

Pages:

119-136

Year*:

2007

VG Wort Pages:


ISBN/ISSN:


Sequence Number:


DOI:

10.1016/j.dam.2006.04.036



Note, Abstract, ©


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



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:

@INPROCEEDINGS{CaragiannisFishkin2007,
AUTHOR = {Caragiannis, Ioannis and Fishkin, Aleksei V. and Kaklamanis, Christos and Papaioannou, Evi},
EDITOR = {Kratochv{\'i}l, Jan and D{\'i}az, Josep and Fiala , Jiř{\'i}},
TITLE = {Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs},
BOOKTITLE = {29th Symposium on Mathematical Foundations of Computer Science MFCS 2004},
PUBLISHER = {Elsevier},
YEAR = {2007},
NUMBER = {2},
VOLUME = {155},
PAGES = {119--136},
SERIES = {Discrete Applied Mathematics},
ADDRESS = {Prague, Czech Republic},
MONTH = {January},
ISBN = {0166-218X},
DOI = {10.1016/j.dam.2006.04.036},
}


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:08:21 PM
Revision
0.



Editor
Anja Becker



Edit Date
07.02.2008 15:15:19