CATS-Apr-15-2016
Title[edit]
Dynamic (1+\epsilon)-Approximate Matchings: A Density Sensitive Approach
Speaker[edit]
Saba Ahmadi
Abstract[edit]
Approximate matchings in fully dynamic graphs have been intensively studied in recent years. In this paper authors present a simple deterministic algorithm whose performance depends on the density of the graph. They maintain fully dynamic (1+\epsilon)-approximate MCM with worst case update time O(\alpha.\epsilon^(-2) ) for graphs with arboricity bounded by \alpha. For the family of bounded arboricity graphs (which includes forests, planar graphs and graphs excluding a fixed minor), in the regime \epsilon = O(1) update time reduces to a constant. This should be contrasted with the previous best 2-approximation results for bounded arboricity graphs, which achieve an O(log n) worst case bound, where n stands for the number of vertices in the graph.
