A parallel maximal matching algorithm for large graphs using Pregel

Byungnam Lim, Yon Dohn Chung

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


Graph matching is to find an independent edge set in a graph. It can be used for various purposes such as finding a cover in a graph, chemical structural computations, multi-level graph partitioning and so on. When a graph is too large to be handled by a single machine, we should use multiple machines. In this paper, we use Pregel, a cloud graph processing architecture which is able to process massive scale graph data in scalable and fault-tolerant ways. We propose a parallel maximal matching algorithm described in the Pregel's vertex-centric BSP model. We test our algorithm on an 8 node cluster and the results show that our algorithm can realize high quality matching for a large graph in a short time. Also, our algorithm is linearly scalable with the number of machines.

Original languageEnglish
Pages (from-to)1910-1913
Number of pages4
JournalIEICE Transactions on Information and Systems
Issue number7
Publication statusPublished - 2014 Jul


  • Matching
  • Parallel matching
  • Pregel

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Vision and Pattern Recognition
  • Electrical and Electronic Engineering
  • Artificial Intelligence

Cite this