An optimal parallel matching algorithm for a convex bipartite graph on a mesh-connected computer

摘要

We address the problem of finding a maximum matching for a convex bipartite graph on a mesh-connected computer (MCC). We show that this can be done in optimal time on MCC by designing the efficient merge and division schemes in bottom-up and top-down approach respectively.