Accession Number:

ADA093097

Title:

On Edge Coloring Bipartite Graphs.

Descriptive Note:

Technical rept.,

Corporate Author:

CORNELL UNIV ITHACA N Y DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1980-11-01

Pagination or Media Count:

12.0

Abstract:

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.

Subject Categories:

  • Computer Programming and Software
  • Human Factors Engineering and Man Machine Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE