Options
Lazy or eager dynamic matching may not be fast
Date Issued
01-10-2020
Author(s)
Kashyop, Manas Jyoti
Indian Institute of Technology, Madras
Abstract
We consider two sub-classes of fully dynamic algorithms for maintaining a maximal matching, which we define as lazy algorithms and eager algorithms. We prove a conditional lower bound which is sub-linear in the number of edges for the update time of lazy algorithms and eager algorithms. Our result is conditioned on the well known conjecture about the hardness of triangle detection in a graph.
Volume
162