We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph in o (√m) time per update. In particular, for minimum vertex cover we provide deterministic data structures for maintaining a (2 + ∈) approximation in O (1ogn/∈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].
Bhattacharya, S., Henzinger, M., Italiano, G.f. (2015). Deterministic fully dynamic data structures for vertex cover and matching. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (pp.785-804). Association for Computing Machinery [10.1137/1.9781611973730.54].
Deterministic fully dynamic data structures for vertex cover and matching
ITALIANO, GIUSEPPE FRANCESCO
2015-01-01
Abstract
We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph in o (√m) time per update. In particular, for minimum vertex cover we provide deterministic data structures for maintaining a (2 + ∈) approximation in O (1ogn/∈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].I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
