3 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…
cs.DS2023
Passes is Optimal for Semi-Streaming Maximal Independent Set
Sepehr Assadi, Christian Konrad, Kheeran K. Naidu +1
In the semi-streaming model for processing massive graphs, an algorithm makes multiple passes over the edges of a given -vertex graph and is tasked with computing the solution t…