Fully dynamic maintenance of vertex cover

DOI10.1007/3-540-57899-4_44MaRDI QIDQ6184397zbMATH OpenOpenAlexFDO

Authors Zoran Ivković, Errol L. Lloyd

Publication date 5 January 2024

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-57899-4_44

zbMATH Keywords

approximation algorithmcompetitive ratiodynamic algorithmmaximal matchingvertex cover

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• Deterministically maintaining a (2 + )-approximate minimum vertex cover in O(1/^2) amortized update time
• Dynamic approximate vertex cover and maximum matching
• Deterministic fully dynamic data structures for vertex cover and matching
• Deterministic fully dynamic data structures for vertex cover and matching
• Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time

Cites work

• A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Depth-first search and the vertex cover problem
• Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps
• Fully dynamic planarity testing with applications
• scientific article; zbMATH DE number 3889282 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256641 (Why is no real title available?)
• Optimization, approximation, and complexity classes
• Reducibility among combinatorial problems

Cited in

(3)

• Fully Dynamic 2-Hop Cover Labeling
• A tight lower bound for 3-coloring grids in the online-LOCAL model
• Recent advances in fully dynamic graph algorithms (invited talk)

This page was built for publication: Fully dynamic maintenance of vertex cover

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