Optimal parallel algorithm for edge-coloring partial k-trees with bounded degrees
Xiao Zhou, Takao Nishizeki · Proceedings of the ... International Symposium on Parallel Architectures, Algorithms, and Networks (ISPAN) · 2002
Many combinatorial problems can be efficiently solved for partial k-trees (graphs of treewidth bounded by k). The edge-coloring problem is one of the well-known combinatorial problems for which no NC algorithms have been obtained for partial k-trees. This paper gives an optimal and first NC parallel algorithm to find an edge-coloring of any given partial k-tree using a minimum number of colors if k and the maximum degree /spl Delta/ are bounded.>