Simple deterministic algorithms for fully dynamic maximal matching Academic Article uri icon

abstract

  • 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 naïve O (n) one was reported up to this date. The only progress in this direction is due to Ivković and Lloyd, who in 1993 devised a deterministic algorithm with an amortized update time of O ((n+m) &sqrt; 2/2), where m is the number of edges. In this article, we show the first deterministic fully dynamic algorithm that outperforms the trivial one. Specifically, we provide a deterministic worst-case update time of O (&sqrt; m). Moreover, our algorithm maintains a matching, which in fact is a 3/2-approximate maximum cardinality matching (MCM). We remark that no fully dynamic algorithm for maintaining (2− ε)-approximate MCM improving upon the …

publication date

  • February 8, 2016