History-Independent Maximal Matchings can be Surprisingly Efficient, and Lead to Better Worst-Case Guarantees
Abstract
One of the most basic problems in dynamic graph algorithms is to maintain a maximal matching as edges are inserted and deleted over time. In a line of work started by Baswana, Gupta and Sen, and then completed by Solomon, it was shown how to solve this problem in amortized expected time \(O(1)\) per update. (Interestingly, achieving worst-case expected \(O(1)\) remains open.)
Fields of Study & Subjects
Graph Theory and Algorithms
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 3999–4022
- Publication date
- 1 January 2026
- Language
- EN