TY - JOUR
T1 - Edge-Coloring Partial k-Trees
AU - Zhou, Xiao
AU - Nakano, Shin Ichi
AU - Nishizek, Takao
N1 - Funding Information:
We thank Dr. Hitoshi Suzuki for various discussions and Dr. Petra Scheffler for suggesting to us to improve the coefficient of the linear sequential time. The comments from the referees greatly helped in improving the presentation of this paper. This research is partly supported by Grant in Aid for Scientific Research of the Ministry of Education, Science, and Culture of Japan under Grant number General Research C) 05650339.
PY - 1996/11
Y1 - 1996/11
N2 - 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 efficient algorithms were previously known, except a polynomial-time algorithm of very high complexity. This paper gives a linear-time sequential algorithm and an optimal parallel algorithm which find an edge-coloring of a given partial k-tree with the minimum number of colors for fixed k. & 1996 Academic Press, Inc.
AB - 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 efficient algorithms were previously known, except a polynomial-time algorithm of very high complexity. This paper gives a linear-time sequential algorithm and an optimal parallel algorithm which find an edge-coloring of a given partial k-tree with the minimum number of colors for fixed k. & 1996 Academic Press, Inc.
UR - http://www.scopus.com/inward/record.url?scp=0037905878&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0037905878&partnerID=8YFLogxK
U2 - 10.1006/jagm.1996.0061
DO - 10.1006/jagm.1996.0061
M3 - Article
AN - SCOPUS:0037905878
SN - 0196-6774
VL - 21
SP - 598
EP - 617
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 3
ER -