Dynamic Approximate Vertex Cover and Maximum Matching
From MaRDI portal
Publication:4933386
DOI10.1007/978-3-642-16367-8_28zbMath1309.68057MaRDI QIDQ4933386
Ronitt Rubinfeld, Krzysztof Onak
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
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
Cites Work
- Unnamed Item
- 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
- 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