Files in this item

FilesDescriptionFormat

application/pdf

application/pdf3301113.pdf (3MB)Restricted to U of Illinois
(no description provided)PDF

Description

Title:Algorithms on Clustering, Orienteering, and Conflict -Free Coloring
Author(s):Chen, Ke
Doctoral Committee Chair(s):Har-Peled, Sariel
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(s):Computer Science
Abstract:In the last part, we present randomized algorithms for online conflict-free coloring of points in the plane, with respect to intervals, halfplanes, congruent disks, and nearly-equal axis-parallel rectangles. In all these cases, the coloring algorithms use O(log n) colors, with high probability. We also present the first efficient deterministic algorithm for the CF coloring of points in the plane with respect to nearly-equal axis-parallel rectangles, using O(log 12 n) colors.
Issue Date:2007
Type:Text
Language:English
Description:102 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2007.
URI:http://hdl.handle.net/2142/81800
Other Identifier(s):(MiAaPQ)AAI3301113
Date Available in IDEALS:2015-09-25
Date Deposited:2007


This item appears in the following Collection(s)

Item Statistics