2010 · 102 citations · 14 references
ComputingComputer ScienceAlgorithmsCombinatoricsData StructuresApproximation AlgorithmsGraph AlgorithmsGraph MiningRandomized Geometric AlgorithmsDynamic Graph AlgorithmsGraph MatchingMatchingMatching AlgorithmsMatching ProblemsRandomized Covering AlgorithmsVertex Cover Approximation
We consider the problem of maintaining a large matching and a small vertex cover in a dynamically changing graph. Each update to the graph is either an edge deletion or an edge insertion. We give the first randomized data structure that simultaneously achieves a constant approximation factor and handles a sequence of K updates in K*polylog(n) time, where n is the number of vertices in the graph. Previous data structures require a polynomial amount of computation per update.
14
Adhi Harmoko S, M.Komp, Joseph Marie Jacquard et al. · 2005 · 18.4K citations
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations
On graph problems in a semi-streaming model
Joan Feigenbaum, Sampath Kannan, Andrew McGregor et al. · Theoretical Computer Science · 2005 · 422 citations
An O (N2.5) algorithm for maximum matching in general graphs
Shimon Even, Oded Kariv · 1975 · 296 citations