Distributed maximum matching verification in CONGEST

DOI10.4230/LIPICS.DISC.2020.37zbMATH Open1540.6816MaRDI QIDQ6535036

Mohamad Ahmadi, Fabian Kuhn

Publication date: 2 November 2023

zbMATH Keywords

distributed graph algorithmsaugmenting pathsdistributed matching

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tight bounds for distributed minimum-weight spanning tree verification
• A fast and simple randomized parallel algorithm for maximal matching
• Matching theory
• Approximating matchings in parallel
• A Local Computation Approximation Scheme to Maximum Matching
• A faster distributed algorithm for computing maximal matchings deterministically
• Distributed Algorithm for Better Approximation of the Maximum Matching
• Local Computation
• Distributed Approximate Matching
• Efficient Distributed Weighted Matchings on Trees
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Approximate Maximum Matching in the CONGEST Model.
• Some simple distributed algorithms for sparse networks
• An improved constant-time approximation algorithm for maximum~matchings
• Round compression for parallel matching algorithms
• Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
• Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
• Paths, Trees, and Flowers
• Online matching: haste makes waste!
• Distributed Approximation of Maximum Independent Set and Maximum Matching
• Distributed verification and hardness of distributed approximation
• Distributed Weighted Matching
• Algorithms – ESA 2004
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Maximum matching and a polyhedron with 0,1-vertices
• Quadratic and near-quadratic lower bounds for the CONGEST model
• Improved deterministic distributed matching via rounding
• Parameterized distributed algorithms

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)