2 papers
cs.DS2026
On the Assadi Liu Tarjan Auction Algorithm for Bipartite Matching: Simplification, Alternative Analysis, and Hard Instance
Christian Konrad, Kheeran K. Naidu, Archie Walton +1
Assadi, Liu, and Tarjan [SOSA'21] gave an auction algorithm that outputs a -approximation to Maximum Matching in bipartite graphs. Their algorithm computes a sequence of $O…
cs.DS2024
Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
Sepehr Assadi, Soheil Behnezhad, Christian Konrad +2
A semi-streaming algorithm in dynamic graph streams processes any -vertex graph by making one or multiple passes over a stream of insertions and deletions to edges of the graph…