39 citations · 78 across the 27 of their papers we have counts for
5 papers · 1 filter
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…