5 citations · 6 across the 6 of their papers we have counts for
7 papers · 1 filter
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(…
Unit Interval Selection in Random Order Streams
Cezar-Mihail Alexandru, Adithya Diddapur, Magnús M. Halldórsson +2
We consider the \textsf{Unit Interval Selection} problem in the one-pass random order streaming model. Here, an algorithm is presented a sequence of unit-length intervals on th…
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…
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…
Space Optimal Vertex Cover in Dynamic Streams
Kheeran K. Naidu, Vihan Shah
We optimally resolve the space complexity for the problem of finding an -approximate minimum vertex cover (MVC) in dynamic graph streams. We give a randomised algorithm for $…
Improved Weighted Matching in the Sliding Window Model
Cezar-Mihail Alexandru, Pavel Dvořák, Christian Konrad +1
We consider the Maximum-weight Matching (MWM) problem in the streaming sliding window model of computation. In this model, the input consists of a sequence of weighted edges on a g…
On Two-Pass Streaming Algorithms for Maximum Bipartite Matching
Christian Konrad, Kheeran K. Naidu
We study two-pass streaming algorithms for Maximum Bipartite Matching (MBM). All known two-pass streaming algorithms for MBM operate in a similar fashion: They compute a maximal ma…