Simple Deterministic Algorithms for Fully Dynamic Maximal Matching

DOI10.1145/2700206zbMath1400.05241arXiv1207.1277MaRDI QIDQ4962204

Ofer Neiman, Shay Solomon

Publication date: 30 October 2018

Published in: ACM Transactions on Algorithms, Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1207.1277

zbMATH Keywords

maximum matching; dynamic algorithms; maximal matching

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms