39 citations · 53 across the 8 of their papers we have counts for
11 papers
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…