Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2008

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: prefix computation

Sortuj według:

Ogranicz wyniki do:

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

Park E., Park K.

Fundamenta Informaticae

2008

Vol. 84, nr 1

81-97

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.