6 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…
Instance-Optimality of Bidirectional PageRank Estimation
Mikkel Thorup, Hanzhi Wang
We study the problem of estimating a vertex's PageRank within a constant relative error, with constant probability. We prove that an adaptive variant of the simple classic bidirect…
Approximate Graph Propagation Revisited: Dynamic Parameterized Queries, Tighter Bounds and Dynamic Updates
Zhuowei Zhao, Zhuo Zhang, Hanzhi Wang +3
We revisit Approximate Graph Propagation (AGP), a unified framework which captures various graph propagation tasks, such as PageRank, feature propagation in Graph Neural Networks (…
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…
Optimal Dynamic Parameterized Subset Sampling
Junhao Gan, Seeun William Umboh, Hanzhi Wang +2
In this paper, we study the Dynamic Parameterized Subset Sampling (DPSS) problem in the Word RAM model. In DPSS, the input is a set,~, of~ items, where each item,~, has a…
Revisiting Local PageRank Estimation on Undirected Graphs: Simple and Optimal
Hanzhi Wang
We propose a simple and optimal algorithm, BackMC, for local PageRank estimation in undirected graphs: given an arbitrary target node in an undirected graph comprising …