Dynamic Approximate Vertex Cover and Maximum Matching

DOI10.1007/978-3-642-16367-8_28zbMath1309.68057MaRDI 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 matching; dynamic algorithms; vertex cover

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68P05: Data structures

68W25: Approximation algorithms

68W20: Randomized algorithms

Related Items

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