Mikkel Thorup

Q: What Schools Are Affiliated With Mikkel Thorup

Mikkel Thorup is affiliated with the following schools: Aarhus University, University of Oxford, University of Copenhagen

Mikkel Thorup's AcademicInfluence.com Rankings

Mikkel Thorup

Computer Science

#1671

World Rank

#1731

Historical Rank

Database

#2843

World Rank

#2968

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Mikkel Thorup's Degrees

PhD Computer Science University of Copenhagen
Masters Computer Science University of Copenhagen

Similar Degrees You Can Earn

Why Is Mikkel Thorup Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Mikkel Thorup is a Danish computer scientist working at University of Copenhagen. He completed his undergraduate education at Technical University of Denmark and his doctoral studies at Oxford University in 1993. From 1993 to 1998, he was at University of Copenhagen and from 1998 to 2013 he was at AT&T Labs-Research in New Jersey. Since 2013 he has been at the University of Copenhagen as a Professor and Head of Center for Efficient Algorithms and Data Structures .

(See a Problem?)

Mikkel Thorup's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Internet traffic engineering by optimizing OSPF weights (2000) (1290)
Optimizing OSPF/IS-IS weights in a changing world (2002) (730)
Approximate distance oracles (2001) (628)
Traffic engineering with traditional IP routing protocols (2002) (534)
Undirected single-source shortest paths with positive integer weights in linear time (1999) (426)
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity (2001) (384)
Compact oracles for reachability and approximate distances in planar digraphs (2001) (310)
Estimating flow distributions from sampled flow statistics (2005) (304)
Increasing Internet Capacity Using Local Search (2004) (295)
Compact routing schemes (2001) (241)
Properties and prediction of flow statistics from sampled packet streams (2002) (239)
Time-space trade-offs for predecessor search (2006) (218)
Charging from sampled network usage (2001) (206)
String Matching in Lempel—Ziv Compressed Strings (1998) (198)
Near-optimal fully-dynamic graph connectivity (2000) (194)
Tabulation based 4-universal hashing with applications to second moment estimation (2004) (182)
On the approximability of numerical taxonomy (fitting distances by tree metrics) (1996) (181)
All Structured Programs have Small Tree-Width and Good Register Allocation (1998) (181)
On RAM priority queues (1996) (176)
Traffic engineering with estimated traffic matrices (2003) (172)
Deterministic Constructions of Approximate Distance Oracles and Spanners (2005) (165)
Rounding algorithms for a geometric embedding of minimum multiway cut (1999) (162)
Integer priority queues with decrease key in constant time and the single source shortest paths problem (2003) (156)
Learn more, sample less: control of volume and variance in network measurement (2005) (152)
Approximate distance oracles (2001) (148)
Dominators in Linear Time (1999) (147)
Estimating flow distributions from sampled flow statistics (2003) (147)
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity (1998) (142)
Maintaining information in fully dynamic trees with top trees (2003) (141)
Spanners and emulators with sublinear distance errors (2006) (136)
Robust optimization of OSPF/IS-IS weights (2003) (132)
The Power of Simple Tabulation Hashing (2010) (131)
An O(n log n) algorithm for the maximum agreement subtree problem for binary trees (1996) (118)
On the Agreement of Many Trees (1995) (112)
Flow sampling under hard resource constraints (2004) (112)
A hybrid genetic algorithm for the weight setting problem in OSPF-IS-IS routing (2005) (108)
Dynamic ordered sets with exponential search trees (2002) (107)
Oracles for Distances Avoiding a Failed Node or Link (2008) (103)
Compact name-independent routing with minimum stretch (2004) (103)
Worst-case update times for fully-dynamic all-pairs shortest paths (2005) (103)
Priority sampling for estimation of arbitrary subset sums (2007) (99)
Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation (2012) (97)
Quick k-Median, k-Center, and Facility Location for Sparse Graphs (2001) (96)
Fully-Dynamic All-Pairs Shortest Paths: Faster and Allowing Negative Cycles (2004) (95)
Tight(er) worst-case bounds on dynamic searching and priority queues (2000) (94)
Undirected single source shortest paths in linear time (1997) (94)
Speeding Up Dynamic Shortest-Path Algorithms (2008) (90)
Randomized sorting in O(n log log n) time and linear space using addition, shift, and bit-wise boolean operations (1997) (90)
A hybrid genetic algorithm for the weight setting problem in OSPF/IS‐IS routing (2005) (87)
Floats, Integers, and Single Source Shortest Paths (1998) (81)
Planning for Fast Connectivity Updates (2007) (81)
Integer sorting in O(n/spl radic/(log log n)) expected time and linear space (2002) (77)
Roundtrip spanners and roundtrip routing in directed graphs (2002) (73)
Heavy Hitters via Cluster-Preserving Clustering (2016) (72)
Fast comparison of evolutionary trees (1994) (69)
OPT versus LOAD in dynamic storage allocation (2003) (68)
Efficient Stream Sampling for Variance-Optimal Estimation of Subset Sums (2008) (67)
Even strongly universal hashing is pretty fast (2000) (65)
Equivalence between priority queues and sorting (2002) (65)
Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search (2014) (64)
Fusion Trees can be Implemented with AC0 Instructions Only (1996) (63)
Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time (2014) (61)
Fully-dynamic min-cut (2001) (61)
The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable (2011) (60)
Load optimal MPLS routing with N + M labels (2003) (60)
Minimizing Diameters of Dynamic Trees (1997) (58)
Intra-domain traffic engineering with shortest path routing protocols (2009) (57)
Changing base without losing space (2010) (57)
Sampling to provide or to bound: With applications to fully dynamic graph algorithms (1997) (56)
Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication (2015) (55)
Survivable IP network design with OSPF routing (2007) (53)
Minimum k-way cuts via deterministic greedy tree packing (2008) (53)
Estimating arbitrary subset sums with few probes (2005) (53)
Higher Lower Bounds for Near-Neighbor and Further Rich Problems (2006) (52)
Randomization does not help searching predecessors (2007) (52)
Decremental dynamic connectivity (1997) (52)
On the k-Independence Required by Linear Probing and Minwise Independence (2010) (51)
Adjacency Labeling Schemes and Induced-Universal Graphs (2014) (51)
Deterministic Edge Connectivity in Near-Linear Time (2014) (48)
Map graphs in polynomial time (1998) (46)
Faster Algorithms for Edge Connectivity via Random 2-Out Contractions (2019) (46)
Faster deterministic sorting and priority queues in linear space (1998) (45)
A Space Saving Trick for Directed Dynamic Transitive Closure and Shortest Path Algorithms (2001) (44)
On Shortcutting Digraphs (1992) (40)
Faster Regular Expression Matching (2009) (38)
String matching in Lempel-Ziv compressed strings (1995) (38)
Optimal evolutionary tree comparison by sparse dynamic programming (1994) (37)
Regular expression matching with multi-strings and intervals (2010) (37)
Bottom-k and priority sampling, set similarity and subset sums with minimal independence (2013) (36)
Parallel Shortcutting of Rooted Trees (1997) (35)
A New Infinity of Distance Oracles for Sparse Graphs (2012) (34)
Maintaining Center and Median in Dynamic Trees (2000) (34)
Dynamic Graph Algorithms with Applications (2000) (34)
Compact name-independent routing with minimum stretch (2008) (33)
Integer Sorting in Expected Time and Linear Space (2002) (33)
Shortcutting Planar Digraphs (1995) (32)
Oracles for distances avoiding a link-failure (2002) (32)
An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms (2001) (31)
Consistent Hashing with Bounded Loads (2016) (31)
Simple Tabulation, Fast Expanders, Double Tabulation, and High Independence (2013) (31)
An Intellectual History of Terror: War, Violence and the State (2010) (30)
On AC0 implementations of fusion trees and atomic heaps (2003) (29)
Faster Worst Case Deterministic Dynamic Connectivity (2015) (29)
Intra-domain traffic engineering with shortest path routing protocols (2013) (29)
Algorithms and estimators for accurate summarization of internet traffic (2007) (29)
More Compact Oracles for Approximate Distances in Undirected Planar Graphs (2013) (29)
Fast Similarity Sketching (2017) (28)
Space efficient dynamic stabbing with fast queries (2003) (28)
Controlled grammatic ambiguity (1994) (28)
Priority sampling estimating arbitrary subset sums (2008) (28)
Finding Cores of Limited Length (1997) (27)
Static dictionaries on AC/sup 0/ RAMs: query time /spl theta/(/spl radic/log n/log log n) is necessary and sufficient (1996) (26)
Twisted Tabulation Hashing (2013) (26)
Fully-Dynamic Min-Cut* (2007) (26)
Practical Hash Functions for Similarity Estimation and Dimensionality Reduction (2017) (25)
String hashing for linear probing (2009) (25)
Discounted deterministic Markov decision processes and discounted all-pairs shortest paths (2009) (24)
High Speed Hashing for Integers and Strings (2015) (24)
Avoiding Ties in Shortest Path First Routing (2003) (24)
Union-Find with Constant Time Deletions (2005) (23)
Direct routing on trees (1998) (23)
Don't rush into a union: take time to find your roots (2011) (23)
Combinatorial Coloring of 3-Colorable Graphs (2012) (22)
Sketching unaggregated data streams for subpopulation-size queries (2007) (22)
Hashing for Statistics over K-Partitions (2014) (22)
Sparse Dynamic Programming for Evolutionary-Tree Comparison (1997) (21)
Coloring 3-Colorable Graphs with Less than n1/5 Colors (2017) (21)
Pro Bono? On philanthrocapitalism as ideological answer to inequality (2013) (21)
Tabulation Based 5-Universal Hashing and Linear Probing (2010) (21)
Performance of estimated traffic matrices in traffic engineering (2003) (21)
Optimal combination of sampled network measurements (2005) (21)
Optimal Pointer Algorithms for Finding Nearest Common Ancestors in Dynamic Trees (1996) (21)
Computing the Agreement of Trees with Bounded Degrees (1995) (20)
Improved Sampling with Applications to Dynamic Graph Algorithms (1996) (20)
Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time (2018) (19)
The power of simple tabulation hashing (2011) (18)
Dynamic Bridge-Finding in Õ(log2 n) Amortized Time (2018) (18)
Quick and good facility location (2003) (18)
From Independence to Expansion and Back Again (2015) (18)
Planar Reachability in Linear Space and Constant Time (2014) (18)
Fast and Powerful Hashing using Tabulation (2015) (18)
Maximum overhang (2007) (17)
Structured Programs have Small Tree-Width and Good Register Allocation (Extended Abstract) (1997) (17)
Approximately Minwise Independence with Twisted Tabulation (2014) (16)
Melding priority queues (2004) (15)
The Power of Two Choices with Simple Tabulation (2014) (14)
Three-in-a-tree in near linear time (2019) (14)
On the Variance of Subset Sum Estimation (2007) (13)
Fortifying OSPF/IS-IS against link-failure (2001) (13)
Disambiguating grammars by exclusion of sub-parse trees (1996) (12)
OSPF Areas Considered Harmful (2003) (12)
Algorithms and estimators for summarization of unaggregated data streams (2014) (12)
Generalized Dominators for Structured Programs (1996) (12)
Coloring 3-colorable graphs with o(n^{1/5}) colors (2014) (11)
Tree based MPLS routing (2003) (10)
Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time (2016) (10)
Confidence intervals for priority sampling (2006) (10)
Black box for constant-time insertion in priority queues (note) (2005) (10)
Untangling the balancing and searching of balanced binary search trees (2003) (10)
Poly-logarithmic deterministic fully-dynamic graph algorithms I: connectivity and minimum spanning tree (1997) (9)
Better Rounding Algorithms for a Geometric Embedding Relaxation of Minimum Multiway Cut (1999) (9)
Combinatorial power in multimedia processors (2003) (9)
Mihai Pǎtraşcu: obituary and open problems (2013) (9)
Sampling to estimate arbitrary subset sums (2005) (9)
Power of d Choices with Simple Tabulation (2018) (9)
Disambiguating grammars by exclusion of sub-parse trees (1996) (9)
The Anarchist and the Partisan—Two Types of Terror in the History of Irregular Warfare (2008) (9)
Random k-out Subgraph Leaves only O(n/k) Inter-Component Edges (2019) (8)
Virtual money (2014) (8)
RAM-Efficient External Memory Sorting (2013) (8)
Dictionaries on AC^0 RAMs: Query Time Theta(√log n/log log n) is Necessary and Sufficient (1997) (7)
On Adaptive Integer Sorting (2004) (7)
Enemy of Humanity: The Anti-Piracy Discourse in Present-Day Anti-Terrorism 1 (2009) (7)
Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space (2002) (7)
Variance optimal sampling based estimation of subset sums (2008) (7)
Confident estimation for multistage measurement sampling and aggregation (2008) (7)
Efficient Preprocessing of Simple Binary Pattern Forests (1994) (7)
Dynamic string searching (2001) (6)
Sampling and Counting Edges via Vertex Accesses (2021) (6)
Fast fencing (2018) (6)
Optimal algorithms for ?nding nearest common ancestors in dynamic trees (2000) (6)
Contested Property Claims: What Disagreement Tells Us About Ownership (2017) (6)
On Conservative Extensions of Syntax in System Development (1991) (6)
Edge sampling and graph parameter estimation via vertex neighborhood accesses (2021) (6)
History of Economic Rationalities: Economic Reasoning as Knowledge and Practice Authority (2017) (6)
Timeouts with time-reversed linear probing (2011) (6)
Equivalence between sorting and priority queues (1995) (5)
Confirmation Sampling for Exact Nearest Neighbor Search (2018) (5)
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor (2021) (5)
Deterministic Worst Case Dynamic Connectivity: Simpler and Faster (2015) (5)
Network design for OSPF routing (5)
Improved Utility Analysis of Private CountSketch (2022) (5)
Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets (2009) (5)
Meldable RAM priority queues and minimum directed spanning trees (2004) (4)
On Conservative Extensions of Syntax in the Process of System Development (1990) (4)
Fast hashing with strong concentration bounds (2019) (4)
Cosmopolitanism: Sovereignty denied or sovereignty restated? (2010) (4)
Compact cactus representations of all non-trivial min-cuts (2018) (4)
Hardness of Bichromatic Closest Pair with Jaccard Similarity (2019) (3)
No Repetition: Fast Streaming with Highly Concentrated Hashing (2020) (3)
Sample (x) = (a*x<=t) is a Distinguisher with Probability 1/8 (2014) (3)
Oracles for Distances Avoiding a Node or Link Failure ∗ (2002) (3)
Load balancing with dynamic set of balls and bins (2021) (3)
Wireless coverage prediction via parametric shortest paths (2018) (3)
Bottleneck Paths and Trees and Deterministic Graphical Games (2016) (3)
Contraction-Based Sparsification in Near-Linear Time (2018) (3)
The Total Enemy: Six Chapters of a Violent Idea (2015) (3)
Introduction: Disagreement as a Window onto Property (2017) (3)
Optimal Decremental Connectivity in Non-Sparse Graphs (2021) (3)
In defence of enmity - critiques of liberal globalism (2006) (2)
Efficient Preprocessing of Simple Binay Pattern Forests (1996) (2)
Fast and powerful hashing using tabulation (2017) (2)
Finding the Maximum Subset with Bounded Convex Curvature (2016) (2)
Sårbarheder: globalisering, militarisering og terrorisering fra murens fald til i dag (2013) (2)
Does Path Cleaning Help in Dynamic All-Pairs Shortest Paths? (2006) (2)
A Pragmatic Implemention of Monotone Priority QueuesArne (1996) (2)
'Delinquents, Troublemakers, Pirates and Gangsters': New Wars in the Postpolitical Borderland (2006) (2)
Nearest neighbor classification using bottom-k sketches (2013) (2)
Compact Oracles for Approximate Distances Around Obstacles in the Plane (2007) (2)
Disks in Curves of Bounded Convex Curvature (2019) (2)
The Promissory Self – Credit and Debt Rationalities in the Work and Life of Karl Marx (2017) (2)
Funding successful research (2013) (1)
Non-Empty Bins with Simple Tabulation Hashing (2018) (1)
Intellectual History of Economic Normativities (2016) (1)
Where did Nazism come from? Tibet? (2007) (1)
Democracy is Surrender Antipolitics as Critique of Liberal Democracy (2013) (1)
Comparative Analysis of Dynamic Graph Techniques and Data Structure (2019) (1)
Dictionaries on AC 0 RAMs : Query Time (1997) (1)
Dynamic Bridge-Finding in $\tilde{O}(\log ^2 n)$ Amortized Time (2017) (1)
Direct Routing on Trees (Extended Abstract) (1998) (1)
Understanding the Moments of Tabulation Hashing via Chaoses (2022) (1)
‘A WORLD WITHOUT SUBSTANCE’ (2005) (1)
Editorial: Violence and Conflict (2008) (1)
Dynamic Ordered Sets with Approximate Queries, Approximate Heaps and Soft Heaps (2019) (1)
Proprietors and parasites (2018) (1)
On sums of monotone random integer variables (2021) (1)
Rousseau and revolution (2011) (1)
Fast and Powerful Hashing Using Tabulation (Invited Talk) (2016) (1)
Eriksen & Stjernfelt: Adskillelsens politik (2009) (0)
Fully Dynamic Exact Edge Connectivity in Sublinear Time (2023) (0)
Reconstructing the Tree of Life (Fitting Distances by Tree Metrics) (Invited Paper) (2022) (0)
An Alternative to Arithmetic Coding with Local Decodability (2010) (0)
Introduction: Profiting from Words (2016) (0)
Maximum Overhang (extended Abstract) (2007) (0)
History of Economic Rationalities (2017) (0)
Session details: Session 9B (2002) (0)
Word encoding tree connectivity works (2000) (0)
The Power of Hashing with Mersenne Primes (2020) (0)
The Entropy of Backwards Analysis (2017) (0)
Linear Probing with 5-Independent Hashing (2015) (0)
How to Cut Corners and Get Bounded Convex Curvature (2016) (0)
Efficient Algorithms and Data Structures (2012) (0)
No Repetition (2022) (0)
The proof of Theorem 2 will be based on a result by Rubinstein [ 9 ] : Assuming the Orthogonal Vectors Conjecture (2019) (0)
46 : 2 Incremental Exact Min-Cut in Poly-logarithmic Amortized (2018) (0)
“Un-kinged himself” (2010) (0)
Poly-logarithmic Deterministic Fully-dynamic Graph Algorithms Ii: 2-edge and Biconnectivity Poly-logarithmic Deterministic Fully-dynamic Graph Algorithms Ii: 2-edge and Biconnectivity (1998) (0)
Session details: Session 7A (2002) (0)
RAM-Efficient External Memory Sorting (2015) (0)
OptimizingOSPF/IS-ISWeightsin aChangingWorld (2002) (0)
Bottleneck paths and trees and deterministic graphical (2018) (0)
Democratic Hatreds (2018) (0)
The History Manifesto - Et symposium (2015) (0)
Fornuftens perversion (2008) (0)
Traktat om de tre bedragere (2018) (0)
2 7 O ct 2 01 8 Deterministic Edge Connectivity in Near-Linear Time ∗ (2018) (0)
Dijkstra’s Single Source Shortest Path Algorithm (2022) (0)
Intellectual history : five questions (2013) (0)
A primal-dual approach for the IGP weight settingproblem (2006) (0)
Roundtrip Routing in Dire ted (2007) (0)
Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming (2023) (0)
No Repetition: Fast and Reliable Sampling with Highly Concentrated Hashing (2022) (0)
Center for Kombinatorisk Optimering - et muligt center i Øresundsregionen, i E. Skarback (ed): (1998) (0)
To Provide or To Bound: Sampling in Fully Dynamic Graph Algorithms (1996) (0)
Intra-domain traffic engineering with shortest path routing protocols (2013) (0)
On Distance Oracles and Routing in Graphs (2002) (0)
Statens idehistorie (2015) (0)
Incremental exact min-cut in poly-logarithmic amortized update (2016) (0)

This paper list is powered by the following services:

Other Resources About Mikkel Thorup

What Schools Are Affiliated With Mikkel Thorup?

Mikkel Thorup is affiliated with the following schools:

Mikkel Thorup's Academic­Influence.com Rankings