Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time

DOI10.1007/978-3-319-59250-3_8zbMath1418.90269arXiv1611.00198OpenAlexW2546514055MaRDI QIDQ2401147

Deeparnab Chakrabarty, Sayan Bhattacharya, Monika R. Henzinger

Publication date: 31 August 2017

Full work available at URL: https://arxiv.org/abs/1611.00198

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (10)

Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching ⋮ Deterministic dynamic matching in worst-case update time ⋮ Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Round Compression for Parallel Matching Algorithms ⋮ Dynamic Matching Algorithms in Practice ⋮ Unnamed Item ⋮ Deterministic dynamic matching in \(O(1)\) update time ⋮ Approximating dynamic weighted vertex cover with soft capacities

This page was built for publication: Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time