Simple deterministic algorithms for fully dynamic maximal matching

DOI10.1145/2700206MaRDI QIDQ6829644zbMATH OpenFDO

Authors Ofer Neiman, Shay Solomon

Publication date 30 October 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2700206

zbMATH Keywords

dynamic algorithmsmaximal matchingmaximum matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Cited in

(7)

• Fully dynamic sequential and distributed algorithms for MAX-CUT
• A tight lower bound for 3-coloring grids in the online-LOCAL model
• Locally computing edge orientations
• Tree-packing revisited: faster fully dynamic min-cut and arboricity
• From theory to practice: engineering approximation algorithms for dynamic orientation
• Near-optimal differentially private graph algorithms via the multidimensional abovethreshold mechanism
• Deterministic k-median clustering in near-optimal time

This page was built for publication: Simple deterministic algorithms for fully dynamic maximal matching

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