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

maximum matchingdynamic algorithmsmaximal matching

Mathematics Subject Classification ID

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

Cited in

(4)

• A tight lower bound for 3-coloring grids in the online-LOCAL model
• Fully dynamic sequential and distributed algorithms for MAX-CUT
• Locally computing edge orientations
• Tree-packing revisited: faster fully dynamic min-cut and arboricity

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)