article

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

Authors:

Eunhui Park,

Kunsoo ParkAuthors Info & Claims

Fundamenta Informaticae, Volume 84, Issue 1

Pages 81 - 97

Published: 01 January 2008 Publication History

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.

References

[1]

Batcher, K. E.: Sorting networks and their applications, Proc. of the 1968 Spring Joint Computer Conference, 32, AFIPS Press, Reston, Va., 1968.

Digital Library

Google Scholar

[2]

Chung, Y., Lee, S.: A boolean circuit for finding a maximum matching in a convex bipartite graph, 2005 Korea-Japan Joint Workshop on Algorithms and Computation (WAAC), 2005.

Google Scholar

[3]

Dekel, E., Sahni, S.: A parallel matching algorithm for convex bipartite graphs and applications to scheduling, J. Parallel and Distributed Computing, 1, 1984, 185-205.

Crossref

Google Scholar

[4]

Dekel, E., Sahni, S.: Parallel scheduling algorithms, J. Operation Research, 31(1), 1984, 24-49.

Digital Library

Google Scholar

[5]

Glover, F.: Maximum matching in convex bipartite graphs, Naval Res. Logist. Quarterly, 14, 1965, 313-316.

Crossref

Google Scholar

[6]

Ladner, R. E., Fischer, M. J.: Parallel prefix computation, J. ACM, 27(4), 1980, 831-838.

Digital Library

Google Scholar

[7]

Lipski Jr., W., Preparata, F. P.: Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems., Acta Inf., 15, 1981, 329-346.

Digital Library

Google Scholar

[8]

Park, K., Park, H., Jeun, W., Ha, S.: Boolean circuit programming: a new paradigm to design parallel algorithms, 15th Australasian Workshop on Combinatorial Algorithms (AWOCA), 2004.

Google Scholar

[9]

Preparata, F. P., Vuillemin, J.: The cube-connected cycles: a versatile network for parallel computation, Commun. ACM, 24(5), 1981, 300-309.

Digital Library

Google Scholar

[10]

Savage, J. E.: Models of Computation: Exploring the Power of Computing, Addison-Wesley, 1998.

Crossref

Google Scholar

[11]

Sipser, M.: Introduction to the Theory of Computation, PWS, 1997.

Digital Library

Google Scholar

Recommendations

An Improved Boolean Circuit for Maximum Matching in a Convex Bipartite Graph
Workshop on Combinatorial Algorithms

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 ...
Computing maximum non-crossing matching in convex bipartite graphs

We consider computing a maximum non-crossing matching in convex bipartite graphs. For a convex bipartite graph of n vertices and m edges, we present an O ( n log n ) time algorithm for finding a maximum non-crossing matching in the graph. The previous ...
Circular convex bipartite graphs

A feedback vertex set is a subset of vertices, such that the removal of this subset renders the remaining graph cycle-free. The weight of a feedback vertex set is the sum of weights of its vertices. Finding a minimum weighted feedback vertex set is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Fundamenta Informaticae Volume 84, Issue 1

Workshop on Combinatorial Algorithms

January 2008

146 pages

ISSN:0169-2968

Issue’s Table of Contents

Publisher

IOS Press

Netherlands

Publication History

Published: 01 January 2008

Author Tags

Qualifiers

Article

Recommendations