4 citations · 5 across the 8 of their papers we have counts for
10 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…
PageRank Centrality in Directed Graphs with Bounded In-Degree
Mikkel Thorup, Hanzhi Wang, Zhewei Wei +1
We study the computational complexity of locally estimating a node's PageRank centrality in a directed graph . For any node , its PageRank centrality is defined as the…
Faster All-Pairs Optimal Electric Car Routing
Dani Dorfman, Haim Kaplan, Robert E. Tarjan +2
We present a randomized -time algorithm for computing \emph{optimal energetic paths} for an electric car between all pairs of vertices in an -vertex directed…
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…
Static to Dynamic Correlation Clustering
Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee +7
Correlation clustering is a well-studied problem, first proposed by Bansal, Blum, and Chawla [Mach. Learn. '04]. The input is an unweighted, undirected graph. The problem is to clu…
Solving the Correlation Cluster LP in Sublinear Time
Nairen Cao, Vincent Cohen-Addad, Shi Li +7
Correlation Clustering is a fundamental and widely-studied problem in unsupervised learning and data mining. The input is a graph and the goal is to construct a clustering minimizi…
Better coloring of 3-colorable graphs
Ken-ichi Kawarabayashi, Mikkel Thorup, Hirotaka Yoneda
We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. This is one of the most challenging problems in graph algorithms. In thi…
Combinatorial Correlation Clustering
Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipczuk +3
Correlation Clustering is a classic clustering objective arising in numerous machine learning and data mining applications. Given a graph , the goal is to partition the ve…
Minimum-cost paths for electric cars
Dani Dorfman, Haim Kaplan, Robert E. Tarjan +2
An electric car equipped with a battery of a finite capacity travels on a road network with an infrastructure of charging stations. Each charging station has a possibly different c…