Authors
Citation
R. Cole et al., Edge-coloring bipartite multigraphs in O(ElogD) time, COMBINATORI, 21(1), 2001, pp. 5-12
Citations number
19
Categorie Soggetti
Mathematics,"Computer Science & Engineering
Journal title
COMBINATORICA
ISSN journal
02099683
→ ACNP
Volume
21
Issue
1
Year of publication
2001
Pages
5 - 12
Database
ISI
SICI code
0209-9683(2001)21:1<5:EBMIOT>2.0.ZU;2-G
Abstract
Let V, E, and D denote the cardinality of the vertex set, the cardinality o
f 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 bipar
tite graph in O(E) time.