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.
| Original language | English |
|---|---|
| Pages (from-to) | 1-13 |
| Journal | Journal of Algorithms |
| Volume | 47 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - Apr 2003 |
Bibliographical note
Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].Funding
* Corresponding author. E-mail address: [email protected] (X. Deng). 1 Research supported in part by an RGC CERG grant (CityU 1056/01E) and an SRG grant (7001040) of City University of Hong Kong. 2 Research partially supported by the NNSF of China and PNSF of Shandong. 3 Supported in part by an RGC.
Research Keywords
- Approximated algorithms
- Path coloring
- Trees of rings
Fingerprint
Dive into the research topics of 'A 2-approximation algorithm for path coloring on a restricted class of trees of rings'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver