39 citations · 78 across the 27 of their papers we have counts for
32 papers
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…
Large-Scale Graph Building in Dynamic Environments: Low Latency and High Quality
Filipe Miguel Gonçalves de Almeida, CJ Carey, Hendrik Fichtenberger +8
Learning and constructing large-scale graphs has attracted attention in recent decades, resulting in a rich literature that introduced various systems, tools, and algorithms. Grale…
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…
Fully Dynamic -Clustering in Update Time
Sayan Bhattacharya, Martín Costa, Silvio Lattanzi +1
We present a -approximate fully dynamic algorithm for the -median and -means problems on metric spaces with amortized update time and worst-case query tim…
Multi-Swap -Means++
Lorenzo Beretta, Vincent Cohen-Addad, Silvio Lattanzi +1
The -means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is often the practitioners' choice algorithm for optimizing the popular -means clustering objective and is know…
Efficient and Stable Fully Dynamic Facility Location
Sayan Bhattacharya, Silvio Lattanzi, Nikos Parotsidis
We consider the classic facility location problem in fully dynamic data streams, where elements can be both inserted and deleted. In this problem, one is interested in maintaining…
A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems
Yuanyuan Dong, Andrew V. Goldberg, Alexander Noe +3
Motivated by a real-world vehicle routing application, we consider the maximum-weight independent set problem: Given a node-weighted graph, find a set of independent (mutually nona…
Near-Optimal Correlation Clustering with Privacy
Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi +4
Correlation clustering is a central problem in unsupervised learning, with applications spanning community detection, duplicate detection, automated labelling and many more. In the…
Optimal Decremental Connectivity in Non-Sparse Graphs
Anders Aaman, Adam Karczmarz, Jakub Łącki +3
We present a dynamic algorithm for maintaining the connected and 2-edge-connected components in an undirected graph subject to edge deletions. The algorithm is Monte-Carlo randomiz…
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor
Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis +2
We consider the numerical taxonomy problem of fitting a positive distance function by a tree metric. We want a tree with positive e…
Correlation Clustering in Constant Many Parallel Rounds
Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrović +3
Correlation clustering is a central topic in unsupervised learning, with many applications in ML and data mining. In correlation clustering, one receives as input a signed graph an…
New instances for maximum weight independent set from a vehicle routing application
Yuanyuan Dong, Andrew V. Goldberg, Alexander Noe +3
We present a set of new instances of the maximum weight independent set problem. These instances are derived from a real-world vehicle routing problem and are challenging to solve…
Planar Reachability Under Single Vertex or Edge Failures
Giuseppe F. Italiano, Adam Karczmarz, Nikos Parotsidis
In this paper we present an efficient reachability oracle under single-edge or single-vertex failures for planar directed graphs. Specifically, we show that a planar digraph ca…
All-Pairs LCA in DAGs: Breaking through the barrier
Fabrizio Grandoni, Giuseppe F. Italiano, Aleksander Łukasiewicz +2
Let be an -vertex directed acyclic graph (DAG). A lowest common ancestor (LCA) of two vertices and is a common ancestor of and such that no descend…
Dynamic Algorithms for the Massively Parallel Computation Model
Giuseppe F. Italiano, Silvio Lattanzi, Vahab S. Mirrokni +1
The Massive Parallel Computing (MPC) model gained popularity during the last decade and it is now seen as the standard model for processing large scale data. One significant shortc…
Dominating Sets and Connected Dominating Sets in Dynamic Graphs
Niklas Hjuler, Giuseppe F. Italiano, Nikos Parotsidis +1
In this paper we study the dynamic versions of two basic graph problems: Minimum Dominating Set and its variant Minimum Connected Dominating Set. For those two problems, we present…
Faster Algorithms for All-Pairs Bounded Min-Cuts
Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano +5
The All-Pairs Min-Cut problem (aka All-Pairs Max-Flow) asks to compute a minimum - cut (or just its value) for all pairs of vertices . We study this problem in directed…
Online Reciprocal Recommendation with Theoretical Performance Guarantees
Fabio Vitale, Nikos Parotsidis, Claudio Gentile
A reciprocal recommendation problem is one where the goal of learning is not just to predict a user's preference towards a passive item (e.g., a book), but to recommend the targete…
Incremental Strong Connectivity and 2-Connectivity in Directed Graphs
Loukas Georgiadis, Giuseppe F. Italiano, Nikos Parotsidis
In this paper, we present new incremental algorithms for maintaining data structures that represent all connectivity cuts of size one in directed graphs (digraphs), and the strongl…
Balancing Information Exposure in Social Networks
Kiran Garimella, Aristides Gionis, Nikos Parotsidis +1
Social media has brought a revolution on how people are consuming news. Beyond the undoubtedly large number of advantages brought by social-media platforms, a point of criticism ha…