File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Dynamic offline conflict-free coloring for unit disks

TitleDynamic offline conflict-free coloring for unit disks
Authors
KeywordsAlgorithms
Approximation algorithms
Color
Coloring
Disks (machine components)
Issue Date2009
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 6th International Workshop on Approximation and Online Algorithms (WAOA 2008), Karlsruhe, Germany, 18-19 September 2008. In Lecture Notes in Computer Science, 2009, v. 5426, p. 241-252 How to Cite?
AbstractA conflict-free coloring for a given set of disks is a coloring of the disks such that for any point p on the plane there is a disk among the disks covering p having a color different from that of the rest of the disks that covers p. In the dynamic offline setting, a sequence of disks is given, we have to color the disks one-by-one according to the order of the sequence and maintain the conflict-free property at any time for the disks that are colored. This paper focuses on unit disks, i.e., disks with radius one. We give an algorithm that colors a sequence of n unit disks in the dynamic offline setting using O(logn) colors. The algorithm is asymptotically optimal because Ω(logn) colors is necessary to color some set of n unit disks for any value of n [9]. © 2009 Springer Berlin Heidelberg.
DescriptionLNCS v. 5426 is Proceedings of the 6th International Workshop, WAOA 2008
WAOA – Audimax A
Persistent Identifierhttp://hdl.handle.net/10722/61203
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorChan, JWTen_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorHong, Xen_HK
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2010-07-13T03:33:05Z-
dc.date.available2010-07-13T03:33:05Z-
dc.date.issued2009en_HK
dc.identifier.citationThe 6th International Workshop on Approximation and Online Algorithms (WAOA 2008), Karlsruhe, Germany, 18-19 September 2008. In Lecture Notes in Computer Science, 2009, v. 5426, p. 241-252en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/61203-
dc.descriptionLNCS v. 5426 is Proceedings of the 6th International Workshop, WAOA 2008-
dc.descriptionWAOA – Audimax A-
dc.description.abstractA conflict-free coloring for a given set of disks is a coloring of the disks such that for any point p on the plane there is a disk among the disks covering p having a color different from that of the rest of the disks that covers p. In the dynamic offline setting, a sequence of disks is given, we have to color the disks one-by-one according to the order of the sequence and maintain the conflict-free property at any time for the disks that are colored. This paper focuses on unit disks, i.e., disks with radius one. We give an algorithm that colors a sequence of n unit disks in the dynamic offline setting using O(logn) colors. The algorithm is asymptotically optimal because Ω(logn) colors is necessary to color some set of n unit disks for any value of n [9]. © 2009 Springer Berlin Heidelberg.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Scienceen_HK
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectAlgorithms-
dc.subjectApproximation algorithms-
dc.subjectColor-
dc.subjectColoring-
dc.subjectDisks (machine components)-
dc.titleDynamic offline conflict-free coloring for unit disksen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.emailTing, HF:hfting@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-540-93980-1_19en_HK
dc.identifier.scopuseid_2-s2.0-60349129580en_HK
dc.identifier.hkuros162179en_HK
dc.identifier.hkuros166278-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-60349129580&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume5426en_HK
dc.identifier.spage241en_HK
dc.identifier.epage252en_HK
dc.publisher.placeGermanyen_HK
dc.description.otherThe 6th International Workshop on Approximation and Online Algorithms (WAOA 2008), Karlsruhe, Germany, 18-19 September 2008. In Lecture Notes in Computer Science, 2009, v. 5426, p. 241-252-
dc.identifier.scopusauthoridChan, JWT=16021445200en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridHong, X=26029441600en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats