On Edge Coloring Bipartite Graphs.

Abstract

An algorithm for finding a minimal edge coloring of a bipartite graph in time O(E log V) is presented. Polynomial time algorithms for this problem have previously been given by Gabow and Kariv the best time bounds being O(E log sq V) and O(V 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1980
Accession Number
ADA093097

Entities

People

  • J. Hopcroft
  • Renee E. Cole

Organizations

  • Department of Computer Science, Cornell University

Tags

Communities of Interest

  • C4I
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Computer Science
  • Computers
  • Coverings
  • Integrals
  • Iterations
  • Military Research
  • New York
  • Polynomials
  • Two Dimensional
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.