Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
Asymptotic Optimality
Degeneration
Online Algorithm
Randomized Algorithm
Subscribe
Academic
Publications
Online ConflictFree Colouring for Hypergraphs
Online ConflictFree Colouring for Hypergraphs,10.1017/S0963548309990587,Combinatorics, Probability & Computing,AMOTZ BARNOYy,Panagiotis Cheilaris,Sv
Edit
Online ConflictFree Colouring for Hypergraphs
(
Citations: 8
)
BibTex

RIS

RefWorks
Download
AMOTZ BARNOYy
,
Panagiotis Cheilaris
,
Svetlana Olonetsky
,
Shakhar Smorodinsky
We provide a framework for online conictfree coloring any hypergraph. We intro duce the notion of degenerate hypergraph, which characterizes hypergraphs that arise in geometry. We use our framework to obtain an ecient randomized
online algorithm
for conictfree coloring any kdegenerate hypergraph with n vertices. Our algorithm uses O(k logn) colors with high probability and this bound is asymptotically optimal, because there are families ofkdegenerate hypergraphs that need that many colors. Moreover, our algorithm uses O(k logk logn) random bits with high probabil ity. As a corollary, we obtain asymptotically optimal randomized algorithms for online conictfree coloring some hypergraphs that arise in geometry. Our algorithm uses exponentially fewer random bits than previous algorithms. We introduce algorithms that are allowed to perform a few recolorings of already colored points. We provide deterministic online conictfree coloring algorithms for points on the line with respect to intervals and for points on the plane with respect to halfplanes (or unit disks) that use O(logn) colors and perform number of recolorings at most linear in n.
Journal:
Combinatorics, Probability & Computing  CPC
, vol. 19, no. 4, pp. 493516, 2010
DOI:
10.1017/S0963548309990587
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
dx.doi.org
)
(
www.informatik.unitrier.de
)
(
www.journals.cambridge.org
)
(
147.102.36.12
)
More »
Citation Context
(3)
...An even more recent result of BarNoy, Cheilaris, and Smorodinsky [
3
] provides a general randomized online CF coloring algorithm, which achieves the same performance as [6] in the special cases just mentioned...
...(a) Theorem 6.1 and the initial encouraging results of Chen, Kaplan, and Sharir [6] and of BarNoy, Cheilaris, and Smorodinsky [
3
], as reviewed in the introduction, raise many interesting open problems, such as the following: (i) Obtain deterministic algorithms with good performance for the cases studied in [6], viz...
Ke Chen
,
et al.
Online ConflictFree Coloring for Intervals
...An even more recent result of Bar Noy et al. [
4
] provides a general randomized online CFcoloring algorithm, which achieves the same performance as [7] in the special cases just mentioned...
...(a) Theorem 6.1, and the initial encouraging results of Chen, Kaplan and Sharir [7] and of Bar Noy et al. [
4
], as reviewed in the introduction, raise many interesting open problems, such as: (i) Obtain deterministic algorithms with good performance for the cases studied in [7], viz...
N. Goodwin
.
Online ConflictFree Coloring for Intervals 1
...An even more recent result of Bar Noy et al. [
4
] provides a general randomized online CFcoloring algorithm, which achieves the same performance as [7] in the special cases just mentioned...
...(a) Theorem 6.1, and the initial encouraging results of Chen, Kaplan and Sharir [7] and of Bar Noy et al. [
4
], as reviewed in the introduction, raise many interesting open problems, such as: (i) Obtain deterministic algorithms with good performance for the cases studied in [7], viz...
Amos Fiat
,
et al.
Online conflictfree coloring for intervals
References
(19)
Conflictfree colorings of shallow discs
(
Citations: 19
)
Noga Alon
,
Shakhar Smorodinsky
Conference:
Symposium on Computational Geometry  SOCG
, pp. 4143, 2006
Conflictfree coloring for intervals: from offline to online
(
Citations: 19
)
Amotz Barnoy
,
Panagiotis Cheilaris
,
Shakhar Smorodinsky
Conference:
ACM Symposium on Parallel Algorithms and Architectures  SPAA
, pp. 128137, 2006
ConflictFree Colorings of Rectangles Ranges
(
Citations: 26
)
Khaled M. Elbassioni
,
Nabil H. Mustafa
Conference:
Symposium on Theoretical Aspects of Computer Science  STACS
, pp. 254263, 2006
ConflictFree Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
(
Citations: 68
)
Guy Even
,
Zvi Lotker
,
Dana Ron
,
Shakhar Smorodinsky
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 691700, 2002
ConflictFree Coloring of Points and Simple Regions in the Plane
(
Citations: 50
)
Sariel Harpeled
,
Shakhar Smorodinsky
Journal:
Discrete & Computational Geometry  DCG
, vol. 34, no. 1, pp. 4770, 2005
Sort by:
Citations
(8)
ConflictFree Coloring Made Stronger
(
Citations: 3
)
Elad Horev
,
Roi Krakovski
,
Shakhar Smorodinsky
Conference:
Scandinavian Workshop on Algorithm Theory  SWAT
, pp. 105117, 2010
The potential to improve the choice: list conflictfree coloring for geometric hypergraphs
Panagiotis Cheilaris
,
Shakhar Smorodinsky
,
Marek Sulovský
Published in 2010.
Dynamic Offline ConflictFree Coloring for Unit Disks
Joseph Wuntat Chan
,
Francis Y. L. Chin
,
Xiangyu Hong
,
Hingfung Ting
Conference:
Workshop on Approximation and Online Algorithms  WAOA
, pp. 241252, 2008
Online ConflictFree Coloring for Intervals
(
Citations: 28
)
Ke Chen
,
Amos Fiat
,
Haim Kaplan
,
Meital Levy
,
Jirí Matousek
,
Elchanan Mossel
,
János Pach
,
Micha Sharir
,
Shakhar Smorodinsky
,
Uli Wagner
,
Emo Welzl
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 36, no. 5, pp. 13421359, 2007
Conflictfree coloring for intervals: from offline to online
(
Citations: 19
)
Amotz Barnoy
,
Panagiotis Cheilaris
,
Shakhar Smorodinsky
Conference:
ACM Symposium on Parallel Algorithms and Architectures  SPAA
, pp. 128137, 2006