Distributed algorithm for approximating the maximum matching

Andrzej Czygrinow, M. Hańćkowiak, E. Szymańska

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


A distributed algorithm to find maximum matching in a graph was presented. The algorithm runs in O(log6n) steps. The network was represented by an undirected graph where each vertex represents a processor and each edge corresponds to a connection between processors in the network. The maximal matching algorithm constructs graph spanners in blocks and use these spanners to compute matchings. An auxiliary multigraph was created to consider mutigraphs instead of simple graphs.

Original languageEnglish (US)
Pages (from-to)62-71
Number of pages10
JournalDiscrete Applied Mathematics
Issue number1-3
StatePublished - Sep 30 2004


  • Distributed algorithm
  • Maximum matching

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Distributed algorithm for approximating the maximum matching'. Together they form a unique fingerprint.

Cite this