5 papers
Instance-Optimality of Bidirectional Dijkstra on Simple Graphs
Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup +2
We study the shortest-path problem on graphs with positive real-valued edge weights. Given a source vertex and a target vertex , the goal is to calculate the length of the s…
Personalized PageRank Estimation in Undirected Graphs
Christian Bertram, Mads Vestergaard Jensen
Given an undirected graph , the Personalized PageRank (PPR) of with respect to , denoted , is the probability that an -discounted random walk…
Dynamic Meta-Kernelization
Christian Bertram, Deborah Haun, Mads Vestergaard Jensen +1
Kernelization studies polynomial-time preprocessing algorithms. Over the last 20 years, the most celebrated positive results of the field have been linear kernels for classical NP-…
Online Metric TSP
Christian Bertram
In the online metric traveling salesperson problem, points of a metric space arrive one by one and have to be placed (immediately and irrevocably) into empty cells of a size-$n…
Estimating Random-Walk Probabilities in Directed Graphs
Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup +2
We study discounted random walks in directed graphs. In each step, the walk either terminates with a constant probability , or proceeds to a random out-neighbor. Our goal is to…