Online Conflict-free Coloring Of Intervals

Please enable javascript in your browser.

This page was sent successfuly

Bookmark

972 viewed

رنگ آمیزی بدون تداخل بر خط بازه ها

972 Viewed

Type of Document: M.Sc. Thesis
Language: Farsi
Document No: 45014 (19)
University: Sharif University of Technology
Department: Computer Engineering
Advisor(s): Abam, Mohammad Ali
Abstract:
In this thesis, we consider the problem of online conflict-free coloring for regions. First, we analyze online variant of the conflict-free coloring of intervals on the line, where each newly inserted interval must be assigned a color upon insertion such that the coloring remains conflict-free, i.e. for every point p in the union of the current intervals, there must be an interval I with a unique color among all intervals covering p. we present deterministic algorithm for achieving this goal which uses O(log^3⁡n) color. Next, we consider the online conflict-free coloring of nearly-equal axis-parallel rectangles in the plane and present a deterministic algorithms which uses O(log^12⁡n) colors. This is the first efficient (i.e, using polylog(n) colors) deterministic online conflict-free coloring for this problem
Keywords:
Conflict-Free-Coloring ; Online Model ; Interval Coloring ; Nearly-Equal Axis Parallel Rectangles

No TOC