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

Myung Ho Kim, Chang Sung Jeong

Research output: Contribution to journalArticlepeer-review


In this paper, we address the problem of finding a maximum matching for a convex bipartite graph on a mesh-connected computer (MCC). We shall 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.

Original languageEnglish
Pages (from-to)129-141
Number of pages13
JournalParallel Algorithms and Applications
Issue number2-3
Publication statusPublished - 1995 Jan 1


  • Convex bipartite graph
  • Distributed memory model
  • Maximum matching
  • Mesh-connected computer
  • Parallel algorithm

ASJC Scopus subject areas

  • Computer Science(all)

Cite this