Deterministic fully dynamic data structures for vertex cover and matching
SIAM J. Comput.(2018)
摘要
We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph in o([EQUATION]m) time per update. In particular, for minimum vertex cover we provide deterministic data structures for maintaining a (2 + ε) approximation in O(log n/ε2) amortized time per update. For maximum matching, we show how to maintain a (3 + ε) approximation in O(m1/3/ε2) amortized time per update, and a (4 + ε) approximation in O(m1/3/ε2) worst-case time per update. Our data structure for fully dynamic minimum vertex cover is essentially near-optimal and settles an open problem by Onak and Rubinfeld [13].
更多查看译文
关键词
fully dynamic algorithms,minimum vertex conver,maximum matching,dynamic data structures,primal-dual method
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要