Distributed maximum matching verification in CONGEST

DOI10.4230/LIPICS.DISC.2020.37MaRDI QIDQ6535036zbMATH OpenFDO

Authors Mohamad Ahmadi, Fabian Kuhn

Publication date 2 November 2023

Full work available at URL https://doi.org/10.4230/LIPICS.DISC.2020.37

zbMATH Keywords

augmenting pathsdistributed graph algorithmsdistributed matching

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Distributed approximate maximum matching in the CONGEST model
• An efficient distributed algorithm for maximum matching in general graphs
• Algorithms – ESA 2004
• Improved Distributed Approximate Matching
• Distributed approximation of maximum independent set and maximum matching

Cites work

• A fast and simple randomized parallel algorithm for maximal matching
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A faster distributed algorithm for computing maximal matchings deterministically
• A Local Computation Approximation Scheme to Maximum Matching
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Algorithms – ESA 2004
• An improved constant-time approximation algorithm for maximum~matchings
• Approximating matchings in parallel
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs
• Distributed Algorithm for Better Approximation of the Maximum Matching
• Distributed approximate matching
• Distributed approximate maximum matching in the CONGEST model
• Distributed approximation of maximum independent set and maximum matching
• Distributed Computing: A Locality-Sensitive Approach
• Distributed verification and hardness of distributed approximation
• Distributed Weighted Matching
• Efficient Distributed Weighted Matchings on Trees
• scientific article; zbMATH DE number 1303560 (Why is no real title available?)
• scientific article; zbMATH DE number 3399279 (Why is no real title available?)
• Improved deterministic distributed matching via rounding
• Local computation: lower and upper bounds
• Locality in Distributed Graph Algorithms
• Matching theory
• Maximum matching and a polyhedron with 0,1-vertices
• Online matching: haste makes waste!
• Parameterized distributed algorithms
• Paths, Trees, and Flowers
• Quadratic and near-quadratic lower bounds for the CONGEST model
• Round compression for parallel matching algorithms
• Some simple distributed algorithms for sparse networks
• Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation
• Survey of distributed decision

This page was built for publication: Distributed maximum matching verification in CONGEST

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