Search filters

List of works by Mikkel Thorup

Approximate distance oracles

Compact cactus representations of all non-trivial min-cuts

scientific article

Compact oracles for reachability and approximate distances in planar digraphs

article published in 2004

Compact routing schemes

Deterministic Edge Connectivity in Near-Linear Time

scholarly article

Dijkstra’s Single Source Shortest Path Algorithm

scientific article published on 13 July 2022

Dominators in Linear Time

scientific article

Dynamic ordered sets with exponential search trees

Edge sampling and graph parameter estimation via vertex neighborhood accesses

scientific article published on 10 June 2022

Equivalence between priority queues and sorting

Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor

scientific article published on 02 January 2024

Fusion trees can be implemented with AC0 instructions only

Higher Lower Bounds for Near-Neighbor and Further Rich Problems

Higher Lower Bounds for Near-Neighbor and Further Rich Problems

How to Cut Corners and Get Bounded Convex Curvature

scientific article published in 2022

Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time

scholarly article published on 12 March 2018

Integer priority queues with decrease key in constant time and the single source shortest paths problem

scholarly article by Mikkel Thorup published November 2004 in Journal of Computer and System Sciences

Load Balancing with Dynamic Set of Balls and Bins ⬇️

scientific article

Maximum Overhang

Near-optimal fully-dynamic graph connectivity

On RAM Priority Queues

On the k-Independence Required by Linear Probing and Minwise Independence

Optimal Pointer Algorithms for Finding Nearest Common Ancestors in Dynamic Trees

scientific article (publication date: May 2000)

Oracles for Distances Avoiding a Failed Node or Link

scientific article (publication date: 2008)

Planar Reachability in Linear Space and Constant Time

scientific article published in October 2015

Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity

scholarly article by Jacob Holm et al published 1 July 2001 in Journal of the ACM

Practical Hash Functions for Similarity Estimation and Dimensionality Reduction ⬇️

scientific article published in January 2017

Randomized Sorting in O(nloglogn) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations

article

Spanners and emulators with sublinear distance errors

String Hashing for Linear Probing

String Matching in Lempel—Ziv Compressed Strings

Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation

article by Mikkel Thorup & Yin Zhang published January 2012 in SIAM Journal on Computing

The Power of Simple Tabulation Hashing

scientific article

The power of simple tabulation hashing

scientific article (publication date: 2011)

Topics in computation

doctoral thesis

Undirected single-source shortest paths with positive integer weights in linear time

Union-Find with Constant Time Deletions

Paulina is supported by:

About Paulina

Help