TY - JOUR
T1 - A Linear Algorithm for Edge-Coloring Series-Parallel Multigraphs
AU - Zhou, Xiao
AU - Suzuki, Hitoshi
AU - Nishizeki, Takao
N1 - Funding Information:
We thank Dr. Shin-ichi Nakano for various comments and for help in preparing the paper. We thank the anonymous referees for many useful comments. This research was partly supported by a Grant in Aid for Scientific Research from the Ministry of Education, Science, and Culture of Japan under Grant Number General Research C) 04650300.
PY - 1996/1
Y1 - 1996/1
N2 - Many combinatorial problems can be efficiently solved for series-parallel multigraphs. However, the edge-coloring problem of finding the minimum number of colors required for edge-coloring given graphs is one of a few well-known combinatorial problems for which no efficient algorithms have been obtained for series-parallel multigraphs. This paper gives a linear algorithm for the problem on series-parallel multigraphs.
AB - Many combinatorial problems can be efficiently solved for series-parallel multigraphs. However, the edge-coloring problem of finding the minimum number of colors required for edge-coloring given graphs is one of a few well-known combinatorial problems for which no efficient algorithms have been obtained for series-parallel multigraphs. This paper gives a linear algorithm for the problem on series-parallel multigraphs.
UR - http://www.scopus.com/inward/record.url?scp=0030360259&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0030360259&partnerID=8YFLogxK
U2 - 10.1006/jagm.1996.0008
DO - 10.1006/jagm.1996.0008
M3 - Article
AN - SCOPUS:0030360259
SN - 0196-6774
VL - 20
SP - 174
EP - 201
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 1
ER -