File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A 2-approximation algorithm for path coloring on a restricted class of trees of rings

TitleA 2-approximation algorithm for path coloring on a restricted class of trees of rings
Authors
Deng, XLi, GZang, WZhou, Y
KeywordsApproximated algorithms
Path coloring
Trees of rings
Issue Date2003
PublisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jalgor
Citation
Journal Of Algorithms, 2003, v. 47 n. 1, p. 1-13 How to Cite?
DOI: http://dx.doi.org/10.1016/S0196-6774(03)00003-8
AbstractA tree of rings is an undirected graph obtained from a tree by replacing each node of the tree with a cycle (called tree-node-cycle) and then contracting the edges of the tree so that two cycles corresponding to the two end-nodes of any edge have precisely one node in common and no three tree-node-cycles share a same node. (A more general definition may allow them to share the same node.) Given a set of paths on a tree of rings, the path coloring problem is to color these paths with the smallest number of colors so that any two paths sharing an edge are assigned different colors. In this paper, we present a 2-approximation algorithm for this problem.
Persistent Identifierhttp://hdl.handle.net/10722/75160
ISSN
0196-6774
2011 Impact Factor: 0.500
ISI Accession Number ID
WOS:000183166700001
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorDeng, Xen_HK
dc.contributor.authorLi, Gen_HK
dc.contributor.authorZang, Wen_HK
dc.contributor.authorZhou, Yen_HK
dc.date.accessioned2010-09-06T07:08:31Z-
dc.date.available2010-09-06T07:08:31Z-
dc.date.issued2003en_HK
dc.identifier.citationJournal Of Algorithms, 2003, v. 47 n. 1, p. 1-13en_HK
dc.identifier.issn0196-6774en_HK
dc.identifier.urihttp://hdl.handle.net/10722/75160-
dc.description.abstractA tree of rings is an undirected graph obtained from a tree by replacing each node of the tree with a cycle (called tree-node-cycle) and then contracting the edges of the tree so that two cycles corresponding to the two end-nodes of any edge have precisely one node in common and no three tree-node-cycles share a same node. (A more general definition may allow them to share the same node.) Given a set of paths on a tree of rings, the path coloring problem is to color these paths with the smallest number of colors so that any two paths sharing an edge are assigned different colors. In this paper, we present a 2-approximation algorithm for this problem.en_HK
dc.languageengen_HK
dc.publisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jalgoren_HK
dc.relation.ispartofJournal of Algorithmsen_HK
dc.subjectApproximated algorithmsen_HK
dc.subjectPath coloringen_HK
dc.subjectTrees of ringsen_HK
dc.titleA 2-approximation algorithm for path coloring on a restricted class of trees of ringsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0196-6774&volume=47&spage=1&epage=13&date=2003&atitle=A+2-Approximation+Algorithm+for+Path+Coloring+on+a+Restricted+Class+of+Trees+of+Ringsen_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.1016/S0196-6774(03)00003-8en_HK
dc.identifier.scopuseid_2-s2.0-0038201510en_HK
dc.identifier.hkuros125052en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0038201510&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume47en_HK
dc.identifier.issue1en_HK
dc.identifier.spage1en_HK
dc.identifier.epage13en_HK
dc.identifier.isiWOS:000183166700001-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridDeng, X=7401768881en_HK
dc.identifier.scopusauthoridLi, G=8835970900en_HK
dc.identifier.scopusauthoridZang, W=7005740804en_HK
dc.identifier.scopusauthoridZhou, Y=7405366693en_HK
dc.identifier.issnl0196-6774-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats