Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds

Fabrizio Grandoni, Chris Schwiegelshohn, Shay Solomon +1

In their breakthrough ICALP'15 paper, Bernstein and Stein presented an algorithm for maintaining a $(3/2+\epsilon )$-approximate maximum matching in fully dynamic {\em bipartite} graphs wi…