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
TitleRandomized Online Algorithms and Lower Bounds for Computing Large Independent Sets in Disk Graphs
Bibtex cite IDRACTI-RU1-2007-46
Journal Discrete Applied Mathematics
Year published 2007
Volume 155
Number 2
Pages 119-136
Keywords On-line algorithms; Competitive analysis; Maximum independent set; Disk graphs
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.
Authors
Caragiannis, Ioannis
Fishkin, A
Kaklamanis, Christos
Papaioannou, Evi
Topics
=SEE CLASSIFICATION DIFFERENCE FROM OTHERS=
Top
BibTeXBibTeX
RISRIS
Attachments
dam.pdf (main file)
 
Publication ID108