点击次数：

所属单位：山东大学数学学院

发表刊物：ACM Transactions on Algorithms (Journal of Algorithms）

关键字：Path coloring, Trees of rings, Approximation algorithms

摘要：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 ...

全部作者：Li, G.,Zang, W.

第一作者：Deng, X.

论文类型：期刊论文

学科门类：理学

一级学科：数学

文献类型：J

卷号：47

期号：1

页面范围：1-13

是否译文：否

发表时间：2003-04-01

收录刊物：SCI