Efficient Algorithms for Finding Maximum Matchings in Convex Bipartite Graphs and Related Problems.
Abstract
A bipartite graph G = (A,B,E) is convex on the vertex set A if A can be ordered so that the elements of A connected to any element b in vertex set B form an interval of A; G is doubly convex if it is convex on both A and B. For these types of graphs Glover discovered a simple rule for finding maximum matchings. Letting abs. val. A = m and abs. val. B = n, in this paper we describe an implementation of Glover's rule which runs in time O(m+nloglogn) on a convex graph, and in time O(m+n) on a doubly convex graph. We also show that, given a maximum matching in a convex bipartite graph G, a corresponding maximum set of independent vertices can be found in time O(m+n). Finally, we briefly discuss some generalizations of convex bipartite graphs and some extensions of the previously discussed techniques to instances in scheduling theory. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1978
- Accession Number
- ADA069860
Entities
People
- Franco P. Preparata
- W. Lipski Jr.
Organizations
- University of Illinois Urbana–Champaign