On Edge Coloring Bipartite Graphs.
CORNELL UNIV ITHACA N Y DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
An algorithm for finding a minimal edge coloring of a bipartite graph in time OE log V is presented. Polynomial time algorithms for this problem have previously been given by Gabow and Kariv the best time bounds being OE log sq V and OV sq log V. The algorithm is based on using fast methods for finding maximal matchings in semiregular bipartite graphs an algorithm for finding a maximal matching in a general bipartite graph was given by Hopcroft and Karp. Two algorithms for finding such a matching are given. Although the second one always has a faster running time, the first one is presented for the sake of clarity.
- Computer Programming and Software
- Human Factors Engineering and Man Machine Systems