An efficient distributed algorithm for maximum matching in general graphs

DOI10.1007/BF01840395MaRDI QIDQ911306zbMATHFDO

Authors 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)

Recommendations

• Algorithms – ESA 2004
• Distributed algorithm for approximating the maximum matching
• Distributed Weighted Matching
• Distributed approximate matching
• scientific article; zbMATH DE number 177842

Cites work

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

Cited in

(10)

• An efficient distributed algorithm for finding all hinge vertices in networks
• scientific article; zbMATH DE number 177842 (Why is no real title available?)
• Algorithms – ESA 2004
• Distributed maximum maintenance on hierarchically divided graphs
• scientific article; zbMATH DE number 1303560 (Why is no real title available?)
• A \(2\cdot | E |\)-bit distributed algorithm for the directed Euler trail problem
• Distributed Algorithm for Better Approximation of the Maximum Matching
• Maintaining bipartite matchings in the presence of failures
• Stabilizing maximum matching in bipartite networks
• Distributed maximum matching verification in CONGEST

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q911306)