An efficient distributed algorithm for maximum matching in general graphs

DOI10.1007/BF01840395zbMath0696.68079MaRDI QIDQ911306

Michael M. Wu, Michael C. Loui

Publication date: 1990

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

combinatorial optimizationmatchinggraph algorithmsdistributed algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Theory of operating systems (68N25)

Related Items (1)

A \(2\cdot | E |\)-bit distributed algorithm for the directed Euler trail problem

Cites Work

• Unnamed Item
• A new distributed depth-first-search algorithm
• The general maximum matching algorithm of Micali and Vazirani
• A \(0(| V | \cdot | E |)\) algorithm for maximum matching of graphs
• TWO THEOREMS IN GRAPH THEORY
• Complexity of network synchronization
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• Paths, Trees, and Flowers
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: An efficient distributed algorithm for maximum matching in general graphs