39 citations · 56 across the 15 of their papers we have counts for
16 papers · 1 filter
Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
Loukas Georgiadis, Evangelos Kipouridis, Evangelos Kosinas +2
Computing edge-connected components in directed and undirected graphs is a fundamental and well-studied problem in graph algorithms. In a very recent breakthrough, Korhonen [STOC 2…
Fully Dynamic Algorithms for Transitive Reduction
Gramoz Goranci, Adam Karczmarz, Ali Momeni +1
Given a directed graph , a transitive reduction of (first studied by Aho, Garey, Ullman [SICOMP `72]) is a minimal subgraph of that preserves the reachability rela…
DynHAC: Fully Dynamic Approximate Hierarchical Agglomerative Clustering
Shangdi Yu, Laxman Dhulipala, Jakub Łącki +1
We consider the problem of maintaining a hierarchical agglomerative clustering (HAC) in the dynamic setting, when the input is subject to point insertions and deletions. We introdu…
Almost Optimal Fully Dynamic -Center Clustering with Recourse
Sayan Bhattacharya, Martín Costa, Ermiya Farokhnejad +2
In this paper, we consider the \emph{metric -center} problem in the fully dynamic setting, where we are given a metric space evolving via a sequence of point insertions…
Fully Dynamic -Clustering with Fast Update Time and Small Recourse
Sayan Bhattacharya, Martín Costa, Naveen Garg +2
In the dynamic metric -median problem, we wish to maintain a set of centers in an input metric space that gets updated via point insertions/deletion…
Dynamic Correlation Clustering in Sublinear Update Time
Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori +1
We study the classic problem of correlation clustering in dynamic node streams. In this setting, nodes are either added or randomly deleted over time, and each node pair is connect…