An Improved Boolean Circuit for Maximum Matching in a Convex Bipartite Graph

Issue title: Workshop on Combinatorial Algorithms

Article type: Research Article

Authors: Park, Eunhui | Park, Kunsoo

Affiliations: Department of Computer Science, University of Maryland College Park, MD 20742, USA. E-mail: [email protected] | School of Computer Science and Engineering, Seoul National University Seoul 151-744, Korea. E-mail: [email protected]

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.

Keywords: Boolean circuit, convex bipartite graph, maximum matching, prefix computation, ASCEND, odd-even merge

Journal: Fundamenta Informaticae, vol. 84, no. 1, pp. 81-97, 2008