Affiliations: Department of Computer Science, University of Maryland
College Park, MD 20742, USA. E-mail: ehpark@cs.umd.edu | School of Computer Science and Engineering, Seoul
National University Seoul 151-744, Korea. E-mail: kpark@theory.snu.ac.kr
Abstract: The Boolean circuit is a simple and realistic model for parallel
computation. Chung and Lee considered the problem of finding a maximum matching
in a convex bipartite graph, which has two sets of vertices, A and B, such that
for any vertex v of A, the neighbors of v in B are contiguous. They gave a
Boolean circuit for the problem in O(log^2 n+log n· log log
n· log b) depth and O(bn^3) size, where n is the number of
vertices in set A of the convex bipartite graph and b is the number of bits
representing a vertex. Using Boolean circuits of prefix computation, odd-even
merge, and some other parallel techniques, we present an improved Boolean
circuit for the same problem in O(log^2 n · (log b + log log n))
depth and O(bn^2 log n) size.
