Fully dynamic maintenance of vertex cover

DOI10.1007/3-540-57899-4_44zbMath1528.68299OpenAlexW1582032289MaRDI QIDQ6184397

Errol L. Lloyd, Zoran Ivković

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 ratiomaximal matchingvertex coverdynamic algorithm

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Depth-first search and the vertex cover problem
• Optimization, approximation, and complexity classes
• Fully dynamic planarity testing with applications
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps
• Reducibility among Combinatorial Problems
• A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs

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