A Linear Algorithm for Edge-Coloring Series-Parallel Multigraphs

Xiao Zhou, Hitoshi Suzuki, Takao Nishizeki

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)174-201
Number of pages28
JournalJournal of Algorithms
Issue number1
Publication statusPublished - 1996 Jan


Dive into the research topics of 'A Linear Algorithm for Edge-Coloring Series-Parallel Multigraphs'. Together they form a unique fingerprint.

Cite this