A linear time algorithm for maximum matchings in convex, bipartite graphs

AbstractThe problem of determining the maximum matching in a convex bipartite graph, G = (V1, V2, E), is considered. It is shown that by using the appropriate data structures, the maximum matching problem can be efficiently transformed into an off-line minimum problem. Since the off-line minimum problem has been shown to be linear, the maximum matching in a convex bipartite graph can be determined in O(|V1|) time