1 citations · 1 across the 4 of their papers we have counts for
4 papers
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…
Near-Optimal Induced Universal Graphs for Bounded Degree Graphs
Mikkel Abrahamsen, Stephen Alstrup, Jacob Holm +2
A graph is an induced universal graph for a family of graphs if every graph in is a vertex-induced subgraph of . For the family of all undirected graphs on verti…
Planar Reachability in Linear Space and Constant Time
Jacob Holm, Eva Rotenberg, Mikkel Thorup
We show how to represent a planar digraph in linear space so that distance queries can be answered in constant time. The data structure can be constructed in linear time. This repr…
Faster Fully-Dynamic Minimum Spanning Forest
Jacob Holm, Eva Rotenberg, Christian Wulff-Nilsen
We give a new data structure for the fully-dynamic minimum spanning forest problem in simple graphs. Edge updates are supported in amortized time per operat…