Showing cs.DSShow all
2 papers · 1 filter
cs.DS2014
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…
cs.DS2014
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…