4 citations · 5 across the 6 of their papers we have counts for
7 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…
Pivot based correlation clustering in the presence of good clusters
David Rasmussen Lolck, Mikkel Thorup, Shuyi Yan
The classic pivot based clustering algorithm of Ailon, Charikar and Chawla [JACM'08] is factor 3, but all concrete examples showing that it is no better than 3 are based on some ve…
Bounding a Polygon by a Minimum Number of Vertices
Mikkel Abrahamsen, Jack Stade, Shuyi Yan +1
Suppose that a polygon is given as an array containing the vertices in counterclockwise order. We analyze how many vertices (including the index of each of these vertices) we 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…
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…
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…