Christian Bertram

collaborators

4 papers

cs.DS2026

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 $I^\pm$ , or proceeds to a random out-neighbor. Our goal is to…

cs.DS2026

Personalized PageRank Estimation in Undirected Graphs

Christian Bertram, Mads Vestergaard Jensen

Given an undirected graph $G = (V, E)$ , the Personalized PageRank (PPR) of $t \in V$ with respect to $s \in V$ , denoted $I ¨ (s, t)$ , is the probability that an $I^\pm$ -discounted random wal…

cs.DS2025

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-…

cs.DS2025

Online Metric TSP

Christian Bertram

In the online metric traveling salesperson problem, $n$ points of a metric space arrive one by one and have to be placed (immediately and irrevocably) into empty cells of a size-$n…