Deterministic fully dynamic data structures for vertex cover and matching
- Submitting institution
-
The University of Warwick
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 5871
- Type
- E - Conference contribution
- DOI
-
10.1137/1.9781611973730.54
- Title of conference / published proceedings
- Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms
- First page
- 785
- Volume
- -
- Issue
- -
- ISSN
- -
- Open access status
- -
- Month of publication
- -
- Year of publication
- 2015
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
2
- Research group(s)
-
T - Theory and Foundations
- Citation count
- -
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Published in the top conference on algorithms, the paper gives the first application of the primal-dual method in a dynamic setting where the input to a problem changes over time. Along with three other papers, it forms the basis of a successful EPSRC grant proposal (EP/S03353X/1). An extended version appears in SIAM Journal on Computing. It is the starting point of a series of results on dynamic fractional matchings by Bhattacharya et al. (ICALP’15, STOC’16, SODA’17), which were ultimately used in the dynamic randomized rounding schemes of Arar, Chechik (Tel Aviv University), Cohen, Stein (Columbia) and Wajc (Carnegie Mellon University).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -