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

• Autorzy: Park E. , Park K.
• Języki publikacji: EN

Abstrakty

EN

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(log2 n +lognźloglognźlogb) depth and O(bn3) 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(log2nź(logb+loglogn)) depth and O(bn2logn) size.

Słowa kluczowe

EN

Boolean circuit; convex bipartite graph; maximum matching; prefix computation; ASCEND; odd-even merge

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 84, nr 1
• Strony: 81--97
• Opis fizyczny: bibliogr. 11 poz., tab., wykr.

Twórcy

autor

Park E.

autor

Park K.

• School of Computer Science and Engineering, Seoul National University, Seoul 151-744, Korea,

Bibliografia

• [1] Batcher, K. E.: Sorting networks and their applications, Proc. of the 1968 Spring Joint Computer Conference, 32, AFIPS Press, Reston, Va., 1968.
• [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.
• [3] Dekel, E., Sahni, S.: A parallelmatching algorithmfor convex bipartite graphs and applications to scheduling, J. Parallel and Distributed Computing, 1, 1984, 185-205.
• [4] Dekel, E., Sahni, S.: Parallel scheduling algorithms, J. Operation Research, 31(1), 1984, 24-49.
• [5] Glover, F.: Maximum matching in convex bipartite graphs, Naval Res. Logist. Quarterly, 14, 1965, 313-316.
• [6] Ladner, R. E., Fischer, M. J.: Parallel prefix computation, J. ACM, 27(4), 1980, 831-838.
• [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.
• [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.
• [9] Preparata, F. P., Vuillemin, J.: The cube-connected cycles: a versatile network for parallel computation, Commun. ACM, 24(5), 1981, 300-309.
• [10] Savage, J. E.: Models of Computation: Exploring the Power of Computing, Addison-Wesley, 1998.
• [11] Sipser, M.: Introduction to the Theory of Computation, PWS, 1997.