2026-08-16T22:20:53Z
https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:13115
2024-03-06T10:51:36Z
ddc:004
open_access
Distributed Maximum Matching Verification in CONGEST
Ahmadi, Mohamad
Kuhn, Fabian
distributed matching
distributed graph algorithms
augmenting paths
We study the maximum cardinality matching problem in a standard distributed setting, where the nodes V of a given n-node network graph G = (V,E) communicate over the edges E in synchronous rounds. More specifically, we consider the distributed CONGEST model, where in each round, each node of G can send an O(log n)-bit message to each of its neighbors. We show that for every graph G and a matching M of G, there is a randomized CONGEST algorithm to verify M being a maximum matching of G in time O(|M|) and disprove it in time O(D + š), where D is the diameter of G and š is the length of a shortest augmenting path. We hope that our algorithm constitutes a significant step towards developing a CONGEST algorithm to compute a maximum matching in time OĢ(s^*), where s^* is the size of a maximum matching.
Schloss Dagstuhl ā Leibniz-Zentrum fĆ¼r Informatik
Mohamad Ahmadi and Fabian Kuhn
2020
Is Part Of LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)
InProceedings
Text
doc-type:ResearchArticle
publishedVersion
application/pdf
doi:10.4230/LIPIcs.DISC.2020.37
urn:nbn:de:0030-drops-131151
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.37
eng
https://creativecommons.org/licenses/by/3.0/legalcode