5 citations · 22 across the 17 of their papers we have counts for
6 papers · 1 filter
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…
Best Laid Plans of Lions and Men
Mikkel Abrahamsen, Jacob Holm, Eva Rotenberg +1
We study the following question dating back to J.E. Littlewood (1885-1977): Can two lions catch a man in a bounded area with rectifiable lakes? The lions and the man are all assume…