4 citations · 23 across the 22 of their papers we have counts for
33 papers
Fully dynamic biconnectivity in time
Jacob Holm, Wojciech Nadara, Eva Rotenberg +1
We present a deterministic fully-dynamic data structure for maintaining information about the cut-vertices in a graph; i.e. the vertices whose removal would disconnect the graph. O…
Adaptive Out-Orientations with Applications
Chandra Chekuri, Aleksander Bjørn Christiansen, Jacob Holm +4
We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that the out-degree of each vertex is bounded. On one hand, we show how to orient the e…
Multilevel Skeletonization Using Local Separators
J. Andreas Bærentzen, Rasmus Emil Christensen, Emil Toftegaard Gæde +1
In this paper we give a new, efficient algorithm for computing curve skeletons, based on local separators. Our efficiency stems from a multilevel approach, where we solve small pro…
Data Structures for Approximate Discrete Fréchet Distance
Ivor van der Hoog, Eva Rotenberg, Sampson Wong
The Fréchet distance is a popular distance measure between curves and . Conditional lower bounds prohibit -approximate Fréchet distance computations in st…
Improved Dynamic Colouring of Sparse Graphs
Aleksander B. G. Christiansen, Krzysztof D. Nowicki, Eva Rotenberg
Given a dynamic graph subject to edge insertions and deletions, we show how to update an implicit representation of a proper vertex colouring, such that colours of vertices are com…
Gapped String Indexing in Subquadratic Space and Sublinear Query Time
Philip Bille, Inge Li Gørtz, Moshe Lewenstein +3
In Gapped String Indexing, the goal is to compactly represent a string of length such that for any query consisting of two strings and , called patterns, and an…