2018/10/02 by Manas Jyoti Kashyop, Kashyop, Manas Jyoti, N. S. Narayanaswamy +1
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.1810.01073
openalex publication_date 2018/10/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a randomized algorithm to maintain a maximal matching without 3 length augmenting paths in the fully dynamic setting. Consequently, we maintain a 3/2 approximate maximum cardinality matching. Our algorithm takes expected amortized O(√(n)) time where n is the number of vertices in the graph when the update sequence is generated by an oblivious adversary. Over any sequence of t edge insertions and deletions presented by an oblivious adversary, the total update time of our algorithm is O(t√(n)) in expectation and O(t√(n) + n log n) with high probability. To the best of our knowledge, our algorithm is the first one to maintain an approximate matching in which all augmenting paths are of length at least 5 in o(√(m)) update time.