Viktor Fredslund-Hansen

collaborators

3 papers

cs.DS2021

Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs

Jacob Evald, Viktor Fredslund-Hansen, Christian Wulff-Nilsen

Given an undirected $n$ -vertex planar graph $G = (V, E, ω)$ with non-negative edge weight function $ω : E \to R$ and given an assigned label to each vertex, a vertex-label…

cs.DS2020

Decremental APSP in Directed Graphs Versus an Adaptive Adversary

Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg +1

Given a directed graph $G = (V, E)$ , undergoing an online sequence of edge deletions with $m$ edges in the initial version of $G$ and $n = ∣ V ∣$ , we consider the problem of maintaini…

cs.DS2020

Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs

Viktor Fredslund-Hansen, Shay Mozes, Christian Wulff-Nilsen

Given an undirected, unweighted planar graph $G$ with $n$ vertices, we present a truly subquadratic size distance oracle for reporting exact shortest-path distances between any pai…