Simple Deterministic Algorithms for Fully Dynamic Maximal Matching

摘要

A maximal matching can be maintained in fully dynamic (supporting both addition and deletion of edges) n vertex graphs using a trivial deterministic"algorithm with a worst-case update time of O(n). No deterministic algorithm that outperforms the naive 0(n) one was reported up to this date. The only progress in this direction is due to Ivkovie and Lloyd, who in 1993 devised a deterministic algorithm with an amortized update time of 0((n + m)boolean AND 5/2), where m is the number of edges.