Dynamic approximate vertex cover and maximum matching

DOI10.1007/978-3-642-16367-8_28MaRDI QIDQ4933386zbMATH OpenOpenAlexFDO

Authors 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

dynamic algorithmsmaximum matchingvertex cover

Mathematics Subject Classification ID

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

Recommendations

• Maintaining a large matching and a small vertex cover
• Deterministic fully dynamic data structures for vertex cover and matching
• Deterministic fully dynamic data structures for vertex cover and matching
• Fully dynamic approximate maximum matching and minimum vertex cover in O(^3 n) worst case update time
• Deterministic dynamic matching in \(O(1)\) update time

Cites work

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

Cited in

(10)

• Shortest augmenting paths for online matchings on trees
• Maintaining a large matching and a small vertex cover
• Faster dynamic matchings and vertex connectivity
• DMVP: Foremost Waypoint Coverage of Time-Varying Graphs
• Deterministic fully dynamic data structures for vertex cover and matching
• Fully Dynamic 2-Hop Cover Labeling
• Optimal lower bounds for matching and vertex cover in dynamic graph streams
• Deterministic fully dynamic data structures for vertex cover and matching
• Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach.
• Fully dynamic maintenance of vertex cover

This page was built for publication: Dynamic approximate vertex cover and maximum matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4933386)