Edge-coloring bipartite multigraphs in O(E log D) time

Richard Cole, Kirstin Ost, Stefan Schirra

Research output: Contribution to journalArticlepeer-review


Let V, E, and D denote the cardinality of the vertex set, the cardinality of the edge set, and the maximum degree of a bipartite multigraph G. We show that a minimal edge-coloring of G can be computed in O(E log D) time. This result follows from an algorithm for finding a matching in a regular bipartite graph in O(E) time.

Original languageEnglish (US)
Pages (from-to)5-12
Number of pages8
Issue number1
StatePublished - 2001

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics


Dive into the research topics of 'Edge-coloring bipartite multigraphs in O(E log D) time'. Together they form a unique fingerprint.

Cite this