Fully dynamic approximate maximum matching and minimum vertex cover in \(O(\log^3 n)\) worst case update time. (English) Zbl 1409.68204
Klein, Philip N. (ed.), Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 470-489 (2017).
MSC:
| 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 |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68W25 | Approximation algorithms |
