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

Title | A 2-approximation algorithm for path coloring on a restricted class of trees of rings |
---|---|

Authors | Deng, X3 Li, G1 Zang, W2 Zhou, Y3 |

Keywords | Approximated algorithms Path coloring Trees of rings |

Issue Date | 2003 |

Publisher | Academic 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 |

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. |

ISSN | 0196-6774 |

DOI | http://dx.doi.org/10.1016/S0196-6774(03)00003-8 |

ISI Accession Number ID | WOS:000183166700001 |

References | References in Scopus |

DC Field | Value |
---|---|

dc.contributor.author | Deng, X |

dc.contributor.author | Li, G |

dc.contributor.author | Zang, W |

dc.contributor.author | Zhou, Y |

dc.date.accessioned | 2010-09-06T07:08:31Z |

dc.date.available | 2010-09-06T07:08:31Z |

dc.date.issued | 2003 |

dc.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. |

dc.description.nature | Link_to_subscribed_fulltext |

dc.identifier.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 |

dc.identifier.doi | http://dx.doi.org/10.1016/S0196-6774(03)00003-8 |

dc.identifier.epage | 13 |

dc.identifier.hkuros | 125052 |

dc.identifier.isi | WOS:000183166700001 |

dc.identifier.issn | 0196-6774 |

dc.identifier.issue | 1 |

dc.identifier.openurl | |

dc.identifier.scopus | eid_2-s2.0-0038201510 |

dc.identifier.spage | 1 |

dc.identifier.uri | http://hdl.handle.net/10722/75160 |

dc.identifier.volume | 47 |

dc.language | eng |

dc.publisher | Academic Press. The Journal's web site is located at http://www.elsevier.com/locate/jalgor |

dc.publisher.place | United States |

dc.relation.ispartof | Journal of Algorithms |

dc.relation.references | References in Scopus |

dc.subject | Approximated algorithms |

dc.subject | Path coloring |

dc.subject | Trees of rings |

dc.title | A 2-approximation algorithm for path coloring on a restricted class of trees of rings |

dc.type | Article |

<?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'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&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+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&selection=ref&src=s&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

- Shandong University
- The University of Hong Kong
- City University of Hong Kong