Dynamic algorithms for graph coloring
- Submitting institution
-
The University of Warwick
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 5873
- Type
- E - Conference contribution
- DOI
-
10.1137/1.9781611975031.1
- Title of conference / published proceedings
- Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
- First page
- 1
- Volume
- -
- Issue
- -
- ISSN
- -
- Open access status
- -
- Month of publication
- -
- Year of publication
- 2018
- 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
-
3
- Research group(s)
-
T - Theory and Foundations
- Citation count
- 50
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Published at the flagship conference on algorithms, the paper gives efficient solutions for two fundamental graph problems in a dynamic setting, where the input changes over time. Along with three other papers, it forms the basis of a successful EPSRC grant proposal (EP/S03353X/1). The dynamic vertex coloring algorithm presented here constitutes an exponential improvement over the update time of the previous best algorithm by Barenboim and Maimon (Open University of Israel). The dynamic edge coloring algorithm presented here is subsequently used to get improved bounds for dynamic matching by Wajc (Carnegie Mellon University) in STOC'20.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -