File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Article: A 2-approximation algorithm for path coloring on a restricted class of trees of rings
  • Basic View
  • Metadata View
  • XML View
TitleA 2-approximation algorithm for path coloring on a restricted class of trees of rings
 
AuthorsDeng, X3
Li, G1
Zang, W2
Zhou, Y3
 
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
 
CitationJournal 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.
 
ISSN0196-6774
 
DOIhttp://dx.doi.org/10.1016/S0196-6774(03)00003-8
 
ISI Accession Number IDWOS:000183166700001
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorDeng, X
 
dc.contributor.authorLi, G
 
dc.contributor.authorZang, W
 
dc.contributor.authorZhou, Y
 
dc.date.accessioned2010-09-06T07:08:31Z
 
dc.date.available2010-09-06T07:08:31Z
 
dc.date.issued2003
 
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.
 
dc.description.naturelink_to_subscribed_fulltext
 
dc.identifier.citationJournal 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
 
dc.identifier.doihttp://dx.doi.org/10.1016/S0196-6774(03)00003-8
 
dc.identifier.epage13
 
dc.identifier.hkuros125052
 
dc.identifier.isiWOS:000183166700001
 
dc.identifier.issn0196-6774
 
dc.identifier.issue1
 
dc.identifier.openurl
 
dc.identifier.scopuseid_2-s2.0-0038201510
 
dc.identifier.spage1
 
dc.identifier.urihttp://hdl.handle.net/10722/75160
 
dc.identifier.volume47
 
dc.languageeng
 
dc.publisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jalgor
 
dc.publisher.placeUnited States
 
dc.relation.ispartofJournal of Algorithms
 
dc.relation.referencesReferences in Scopus
 
dc.subjectApproximated algorithms
 
dc.subjectPath coloring
 
dc.subjectTrees of rings
 
dc.titleA 2-approximation algorithm for path coloring on a restricted class of trees of rings
 
dc.typeArticle
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Deng, X</contributor.author>
<contributor.author>Li, G</contributor.author>
<contributor.author>Zang, W</contributor.author>
<contributor.author>Zhou, Y</contributor.author>
<date.accessioned>2010-09-06T07:08:31Z</date.accessioned>
<date.available>2010-09-06T07:08:31Z</date.available>
<date.issued>2003</date.issued>
<identifier.citation>Journal Of Algorithms, 2003, v. 47 n. 1, p. 1-13</identifier.citation>
<identifier.issn>0196-6774</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/75160</identifier.uri>
<description.abstract>A 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.</description.abstract>
<language>eng</language>
<publisher>Academic Press. The Journal&apos;s web site is located at http://www.elsevier.com/locate/jalgor</publisher>
<relation.ispartof>Journal of Algorithms</relation.ispartof>
<subject>Approximated algorithms</subject>
<subject>Path coloring</subject>
<subject>Trees of rings</subject>
<title>A 2-approximation algorithm for path coloring on a restricted class of trees of rings</title>
<type>Article</type>
<identifier.openurl>http://library.hku.hk:4550/resserv?sid=HKU:IR&amp;issn=0196-6774&amp;volume=47&amp;spage=1&amp;epage=13&amp;date=2003&amp;atitle=A+2-Approximation+Algorithm+for+Path+Coloring+on+a+Restricted+Class+of+Trees+of+Rings</identifier.openurl>
<description.nature>link_to_subscribed_fulltext</description.nature>
<identifier.doi>10.1016/S0196-6774(03)00003-8</identifier.doi>
<identifier.scopus>eid_2-s2.0-0038201510</identifier.scopus>
<identifier.hkuros>125052</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-0038201510&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>47</identifier.volume>
<identifier.issue>1</identifier.issue>
<identifier.spage>1</identifier.spage>
<identifier.epage>13</identifier.epage>
<identifier.isi>WOS:000183166700001</identifier.isi>
<publisher.place>United States</publisher.place>
</item>
Author Affiliations
  1. Shandong University
  2. The University of Hong Kong
  3. City University of Hong Kong