10 citations · 16 across the 7 of their papers we have counts for
12 papers · 1 filter
Dynamic PageRank: Algorithms and Lower Bounds
Rajesh Jayaram, Jakub Łącki, Slobodan Mitrović +2
We consider the PageRank problem in the dynamic setting, where the goal is to explicitly maintain an approximate PageRank vector for a graph under a sequence of…
Fully Dynamic Consistent -Center Clustering
Jakub Łącki, Bernhard Haeupler, Christoph Grunau +2
We study the consistent k-center clustering problem. In this problem, the goal is to maintain a constant factor approximate -center solution during a sequence of point inser…
Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time
Laxman Dhulipala, David Eisenstat, Jakub Łącki +2
We study the widely used hierarchical agglomerative clustering (HAC) algorithm on edge-weighted graphs. We define an algorithmic framework for hierarchical agglomerative graph clus…
Fully Dynamic Matching: Beating 2-Approximation in Update Time
Soheil Behnezhad, Jakub Łącki, Vahab Mirrokni
In fully dynamic graphs, we know how to maintain a 2-approximation of maximum matching extremely fast, that is, in polylogarithmic update time or better. In a sharp contrast and de…
Near-Optimal Massively Parallel Graph Connectivity
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari +2
Identifying the connected components of a graph, apart from being a fundamental problem with countless applications, is a key primitive for many other algorithms. In this paper, we…
Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
Adam Karczmarz, Jakub Łącki
We give new partially-dynamic algorithms for the all-pairs shortest paths problem in weighted directed graphs. Most importantly, we give a new deterministic incremental algorithm f…