Using euler partitions to edge color bipartite multigraphs |
| |
| Authors: | Harold N Gabow |
| |
| Affiliation: | (1) Department of Computer Science, University of Colorado, Boulder, Colorado |
| |
| Abstract: | An algorithm for finding a minimal edge coloring of a bipartite multigraph is presented. The algorithm usesO(V
1/2
ElogV + V) time andO(E + V) space. It is based on a divide-and-conquer strategy, using euler partitions to divide the graph. A modification of the algorithm for matching is described. This algorithm finds a maximum matching of a regular bipartite graph with all degrees 2n, inO(E + V) time andO(E + V) space.This work was partially supported by the National Science Foundation under Grant GJ36461. |
| |
| Keywords: | Edge coloring euler partition matching divide-and-conquer multigraph regular bipartite graph |
| 本文献已被 SpringerLink 等数据库收录！ |
