AN NC PARALLEL ALGORITHM FOR EDGE-COLORING SERIES-PARALLEL MULTIGRAPHS

Authors
ZHOU X SUZUKI H NISHIZEKI T
Citation
X. Zhou et al., AN NC PARALLEL ALGORITHM FOR EDGE-COLORING SERIES-PARALLEL MULTIGRAPHS, Journal of algorithms, 23(2), 1997, pp. 359-374
Citations number
23
Categorie Soggetti
Mathematics,Mathematics,"Computer Science Theory & Methods
Journal title
Journal of algorithms → ACNP
ISSN journal
01966774
Volume
23
Issue
2
Year of publication
1997
Pages
359 - 374
Database
ISI
SICI code
0196-6774(1997)23:2<359:ANPAFE>2.0.ZU;2-V
Abstract
Many combinatorial problems can be efficiently solved in parallel for series-parallel multigraphs. The edge-coloring problem is one of a few combinatorial problems for which no NC parallel algorithm has been ob tained for series-parallel multigraphs. This paper gives an NC paralle l algorithm for the problem on series-parallel multigraphs G. It takes O(log n) time with O(Delta n/log n) processors, where n is the number of vertices and Delta is the maximum degree of G. (C) 1997 Academic P ress.