What is it about?
A matching is a set of edges with no overlapping vertices. A maximal matching is a matching that intersects all edges in the graph. We give a new algorithm for maintaining a parallel maximal matching on a graph that is changing over time (the parallel batch-dynamic setting). We prove that the amount of (expected amortized) compute our algorithm takes is optimal on standard (r=2) graphs.
Featured Image
Photo by Alina Grubnyak on Unsplash
Why is it important?
Today’s world has many large graphs that change over time (ex. consider the graph where vertices are webpages, and edges connect two webpages if one links to the other). One reason the parallel batch-dynamic model is interesting is because it naturally expresses this setting. Parallel batch-dynamic algorithms have also been successfully used as subroutines in static parallel algorithms. Through analyzing matching, this paper serves as an introduction to the parallel batch-dynamic algorithms literature, and is ideal for researchers interested in learning more about the area.
Read the Original
This page is a summary of: Parallel Batch-Dynamic Maximal Matching with Constant Work per Update, July 2025, ACM (Association for Computing Machinery),
DOI: 10.1145/3694906.3743313.
You can read the full text:
Contributors
The following have contributed to this page
