5 citations · 22 across the 17 of their papers we have counts for
22 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…
Splay Top Trees
Jacob Holm, Eva Rotenberg, Alice Ryhl
The top tree data structure is an important and fundamental tool in dynamic graph algorithms. Top trees have existed for decades, and today serve as an ingredient in many state-of-…
Worst-case Deterministic Fully-Dynamic Planar 2-vertex Connectivity
Jacob Holm, Ivor van der Hoog, Eva Rotenberg
We study dynamic planar graphs with vertices, subject to edge deletion, edge contraction, edge insertion across a face, and the splitting of a vertex in specified corners. We d…
Adaptive Out-Orientations with Applications
Aleksander B. G. Christiansen, Jacob Holm, Ivor van der Hoog +2
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…
Massively Parallel Computation on Embedded Planar Graphs
Jacob Holm, Jakub Tětek
Many of the classic graph problems cannot be solved in the Massively Parallel Computation setting (MPC) with strongly sublinear space per machine and rounds, unless the…