File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Perfect circular arc coloring

TitlePerfect circular arc coloring
Authors
Chen, XHu, ZZang, W
KeywordsCircular-arc graph
Complexity
Graph coloring
Matching
Perfect graph
Issue Date2005
PublisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905
Citation
Journal Of Combinatorial Optimization, 2005, v. 9 n. 3, p. 267-280 How to Cite?
DOI: http://dx.doi.org/10.1007/s10878-005-1411-x
AbstractThe circular arc coloring problem is to find a minimum coloring of a set of arcs of a circle so that no two overlapping arcs share a color. This NP-hard problem arises in a rich variety of applications and has been studied extensively. In this paper we present an O(n 2 m) combinatorial algorithm for optimally coloring any set of arcs that corresponds to a perfect graph, and propose a new approach to the general circular arc coloring problem. © 2005 Springer Science + Business Media, Inc.
Persistent Identifierhttp://hdl.handle.net/10722/75148
ISSN
1382-6905
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.370
ISI Accession Number ID
WOS:000230175400003
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorChen, Xen_HK
dc.contributor.authorHu, Zen_HK
dc.contributor.authorZang, Wen_HK
dc.date.accessioned2010-09-06T07:08:23Z-
dc.date.available2010-09-06T07:08:23Z-
dc.date.issued2005en_HK
dc.identifier.citationJournal Of Combinatorial Optimization, 2005, v. 9 n. 3, p. 267-280en_HK
dc.identifier.issn1382-6905en_HK
dc.identifier.urihttp://hdl.handle.net/10722/75148-
dc.description.abstractThe circular arc coloring problem is to find a minimum coloring of a set of arcs of a circle so that no two overlapping arcs share a color. This NP-hard problem arises in a rich variety of applications and has been studied extensively. In this paper we present an O(n 2 m) combinatorial algorithm for optimally coloring any set of arcs that corresponds to a perfect graph, and propose a new approach to the general circular arc coloring problem. © 2005 Springer Science + Business Media, Inc.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905en_HK
dc.relation.ispartofJournal of Combinatorial Optimizationen_HK
dc.subjectCircular-arc graphen_HK
dc.subjectComplexityen_HK
dc.subjectGraph coloringen_HK
dc.subjectMatchingen_HK
dc.subjectPerfect graphen_HK
dc.titlePerfect circular arc coloringen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1382-6905&volume=9&spage=267&epage=280&date=2005&atitle=Perfect+Circular+Arc+Coloringen_HK
dc.identifier.emailZang, W:wzang@maths.hku.hken_HK
dc.identifier.authorityZang, W=rp00839en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/s10878-005-1411-xen_HK
dc.identifier.scopuseid_2-s2.0-22044448734en_HK
dc.identifier.hkuros108647en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-22044448734&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume9en_HK
dc.identifier.issue3en_HK
dc.identifier.spage267en_HK
dc.identifier.epage280en_HK
dc.identifier.isiWOS:000230175400003-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridChen, X=8987182300en_HK
dc.identifier.scopusauthoridHu, Z=44960958800en_HK
dc.identifier.scopusauthoridZang, W=7005740804en_HK
dc.identifier.citeulike243502-
dc.identifier.issnl1382-6905-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats