Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching

Sayan Bhattacharya, Monika Henzinger, Giuseppe F. Italiano

Type: Preprint

Publication Date: 2014-12-22

Citations: 35

DOI: https://doi.org/10.1137/1.9781611973730.54

Locations

arXiv (Cornell University) - View - PDF
Warwick Research Archive Portal (University of Warwick) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Deterministic fully dynamic data structures for vertex cover and matching	2015	Sayan Bhattacharya Monika Henzinger Giuseppe F. Italiano
+ PDF Chat	Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching	2018	Sayan Bhattacharya Monika Henzinger Giuseppe F. Italiano
+	Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching	2014	Sayan Bhattacharya Monika Henzinger Giuseppe F. Italiano
+	Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in $O(\log^3 n)$ Worst Case Update Time	2017	Sayan Bhattacharya Monika Henzinger Danupon Nanongkai
+	Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in $O(1)$ Amortized Update Time	2016	Sayan Bhattacharya Deeparnab Chakrabarty Monika Henzinger
+	Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in $O(1)$ Amortized Update Time	2016	Sayan Bhattacharya Deeparnab Chakrabarty Monika Henzinger
+ PDF Chat	Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time	2017	Sayan Bhattacharya Deeparnab Chakrabarty Monika Henzinger
+ PDF Chat	Fully Dynamic Maximal Matching in O (log n) Update Time	2011	Surender Baswana Manoj Gupta Sandeep Sen
+	Fully dynamic maximal matching in O(log n) update time	2011	Surender Baswana Manoj Gupta Sandeep Sen
+	Fully Dynamic $(1+ε)$-Approximate Matchings	2013	Manoj Gupta Richard Peng
+ PDF Chat	Fully Dynamic Maximal Matching in $O(\log n)$ Update Time	2015	Surender Baswana Manoj Gupta Sandeep Sen
+ PDF Chat	Dynamic Algorithms for Maximum Matching Size	2023	Soheil Behnezhad
+ PDF Chat	Simple Deterministic Algorithms for Fully Dynamic Maximal Matching	2015	Ofer Neiman Shay Solomon
+ PDF Chat	New deterministic approximation algorithms for fully dynamic matching	2016	Sayan Bhattacharya Monika Henzinger Danupon Nanongkai
+	New Deterministic Approximation Algorithms for Fully Dynamic Matching	2016	Sayan Bhattacharya Monika Henzinger Danupon Nanongkai
+	New Deterministic Approximation Algorithms for Fully Dynamic Matching	2016	Sayan Bhattacharya Monika Henzinger Danupon Nanongkai
+	Fully Dynamic $(1+\epsilon)$-Approximate Matchings	2013	Manoj Gupta Richard Peng
+	Simple Deterministic Algorithms for Fully Dynamic Maximal Matching	2012	Ofer Neiman Shay Solomon
+	Simple Deterministic Algorithms for Fully Dynamic Maximal Matching	2012	Ofer Neiman Shay Solomon
+	Deterministic Dynamic Matching In Worst-Case Update Time	2021	P. Kiss

Works That Cite This (18)

Action	Title	Year	Authors
+ PDF Chat	Dynamic Clustering to Minimize the Sum of Radii	2020	Monika Henzinger Dariusz Leniowski Claire Mathieu
+ PDF Chat	Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time	2017	Sayan Bhattacharya Deeparnab Chakrabarty Monika Henzinger
+ PDF Chat	Design of Dynamic Algorithms via Primal-Dual Method	2015	Sayan Bhattacharya Monika Henzinger Giuseppe F. Italiano
+ PDF Chat	Fully Dynamic Maximal Matching in Constant Update Time	2016	Shay Solomon
+ PDF Chat	Fully Dynamic Matching in Bipartite Graphs	2015	Aaron Bernstein Clifford Stein
+ PDF Chat	Round compression for parallel matching algorithms	2018	Artur Czumaj Jakub Łącki Aleksander Mądry Slobodan Mitrović Krzysztof Onak Piotr Sankowski
+ PDF Chat	Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms	2016	Amir Abboud Søren Dahlgaard
+	Round Compression for Parallel Matching Algorithms	2017	Artur Czumaj Jakub Łącki Aleksander Mądry Slobodan Mitrović Krzysztof Onak Piotr Sankowski
+	Optimal Dynamic Distributed MIS	2015	Keren Censor-Hillel Elad Haramaty Zohar Karnin
+	Distributed PCP Theorems for Hardness of Approximation in P	2017	Amir Abboud Aviad Rubinstein Ryan Williams

Works Cited by This (5)

Action	Title	Year	Authors
+ PDF Chat	Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back	2013	Aleksander Mądry
+ PDF Chat	Simple deterministic algorithms for fully dynamic maximal matching	2013	Ofer Neiman Shay Solomon
+ PDF Chat	Fully Dynamic Maximal Matching in O (log n) Update Time	2011	Surender Baswana Manoj Gupta Sandeep Sen
+ PDF Chat	Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems	2014	Amir Abboud Virginia Vassilevska Williams
+	Simple Deterministic Algorithms for Fully Dynamic Maximal Matching	2012	Ofer Neiman Shay Solomon