Dynamic Approximate Vertex Cover and Maximum Matching

DOI10.1007/978-3-642-16367-8_28zbMath1309.68057OpenAlexW2121961571MaRDI QIDQ4933386

Krzysztof Onak, Ronitt Rubinfeld

Publication date: 12 October 2010

Published in: Property Testing (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1721.1/73896

zbMATH Keywords

maximum matchingdynamic algorithmsvertex cover

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (1)

Shortest augmenting paths for online matchings on trees

Cites Work

• Unnamed Item
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• A fully dynamic approximation scheme for shortest paths in planar graphs
• On graph problems in a semi-streaming model
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Worst-case update times for fully-dynamic all-pairs shortest paths
• Sparsification—a technique for speeding up dynamic graph algorithms
• Weighted Matching in the Semi-Streaming Model
• Fully-dynamic min-cut
• Distributed approximate matching
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

This page was built for publication: Dynamic Approximate Vertex Cover and Maximum Matching