Algorithms for edge coloring bipartite graphs
- 1 January 1978
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 184-192
- https://doi.org/10.1145/800133.804346
Abstract
A minimum edge coloring of a bipartite graph is a partition of the edges into &Dgr; matchings, where &Dgr; is the maximum degree in the graph. Coloring algorithms are presented that use time O(min(¦E¦ &Dgr; log n, ¦E¦ @@@@n log n, n2log &Dgr;)) and space O(n&Dgr;). This compares favorably to the previous O(¦E¦ [equation] log &Dgr;) time bound. The coloring algorithms also find maximum matchings on regular (or semi-regular) bipartite graphs. The time bounds compare favorably to the O(¦E¦ @@@@n) matching algorithm, expect when [equation] ≤ &Dgr; ≤ @@@@n log n.This publication has 0 references indexed in Scilit: