An improved Boolean circuit for maximum matching in a convex bipartite graph
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 nu of A, the neighbors of nu in B are contiguous. They gave a Boolean circuit for the problem in O(log(2) n + logn.log logn.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.
boolean circuit maximum matching convex bipartite graph prefix computation odd-even merge ascend