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.
