4 citations · 23 across the 22 of their papers we have counts for
7 papers · 1 filter
The Bane of Low-Dimensionality Clustering
Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg +1
In this paper, we give a conditional lower bound of on running time for the classic k-median and k-means clustering objectives (where n is the size of the input), even i…
One-Way Trail Orientations
Anders Aamand, Niklas Hjuler, Jacob Holm +1
Given a graph, does there exist an orientation of the edges such that the resulting directed graph is strongly connected? Robbins' theorem [Robbins, Am. Math. Monthly, 1939] states…
Dynamic Bridge-Finding in Amortized Time
Jacob Holm, Eva Rotenberg, Mikkel Thorup
We present a deterministic fully-dynamic data structure for maintaining information about the bridges in a graph. We support updates in amortized time, and…
Online Bipartite Matching with Amortized Replacements
Aaron Bernstein, Jacob Holm, Eva Rotenberg
In the online bipartite matching problem with replacements, all the vertices on one side of the bipartition are given, and the vertices on the other side arrive one by one with all…
Contracting a Planar Graph Efficiently
Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz +3
We present a data structure that can maintain a simple planar graph under edge contractions in linear total time. The data structure supports adjacency queries and provides access…
Dynamic Planar Embeddings of Dynamic Graphs
Jacob Holm, Eva Rotenberg
We present an algorithm to support the dynamic embedding in the plane of a dynamic graph. An edge can be inserted across a face between two vertices on the face boundary (we call s…