×
Author ID: thorup.mikkel Recent zbMATH articles by "Thorup, Mikkel"
Published as: Thorup, Mikkel; Thorup, M.
External Links: MGP · Wikidata · dblp · GND
all top 5

Co-Authors

38 single-authored
19 Zwick, Uri
16 Alstrup, Stephen
10 Patrascu, Mihai
9 Farach, Martin
7 Holm, Jacob
7 Kawarabayashi, Ken-ichi
6 Aamand, Anders
6 Kaplan, Haim
5 de Lichtenberg, Kristian
5 Duffield, Nick G.
5 Lund, Carsten
4 Abrahamsen, Mikkel
4 Andersson, Arne A.
4 Karger, David R.
4 Knudsen, Mathias Bæk Tejs
4 Lauridsen, Peter W.
4 Paterson, Mike S.
4 Rauch Henzinger, Monika
3 Buriol, Luciana S.
3 Cohen, Edith
3 Demetrescu, Camil
3 Fortz, Bernard
3 Mendelson, Ran
3 Pagh, Rasmus
3 Przytycka, Teresa M.
3 Rauhe, Theis
3 Resende, Mauricio G. C.
3 Rotenberg, Eva
3 Zhang, Yin
2 Agarwala, Richa
2 Altın, Ayşegül
2 Arge, Lars
2 Bafna, Vineet
2 Bille, Philip
2 Buchsbaum, Adam L.
2 Cohen-Addad, Vincent
2 Dahlgaard, Søren
2 Goranci, Gramoz
2 Gørtz, Inge Li
2 Karloff, Howard J.
2 Kenyon, Claire M.
2 King, Valerie
2 Klein, Philip N.
2 Knudsen, Jakob Bæk Tejs
2 Madani, Omid
2 Peres, Yuval
2 Reingold, Nick
2 Roditty, Liam
2 Stein, Clifford
2 Tarjan, Robert Endre
2 ümit, Hakan
2 Winkler, Peter M.
2 Young, Neal E.
2 Zamir, Or
1 Abraham, Ittai
1 Adamaszek, Anna
1 Alon, Noga
1 Blikle, Andrzej Jacek
1 Boyle, Elette
1 Bringmann, Karl
1 Bro Miltersen, Peter
1 Chechik, Shiri
1 Chowdhury, Rezaul Alam
1 Christiani, Tobias
1 Cole, Richard John
1 Dodis, Yevgeniy
1 Farach-Colton, Martin
1 Faruolo, Pompeo
1 Gavoille, Cyril
1 Ghaffari, Mohsen
1 Harel, Dov
1 Hariharan, Ramesh
1 Houen, Jakob Bæk Tejs
1 Husfeldt, Thore
1 Italiano, Giuseppe Francesco
1 Iyer, Raj D. jun.
1 Kejlberg-Rasmussen, Casper
1 Kolla, Alexandra
1 Kopelowitz, Tsvi
1 Kutten, Shay
1 Lai, Kai-Yuan
1 Lo, On-Hei Solomon
1 Lu, Hsueh-I
1 Malkhi, Dahlia
1 Mehr, Mehran
1 Mirrokni, Vahab S.
1 Narayanan, Babu O.
1 Nisan, Noam
1 Nowicki, Krzysztof
1 Pagh, Anna
1 Pettie, Seth
1 Rahul, Hariharan S.
1 Ramachandran, Vijaya
1 Rasmussen, Peter Michael Reichstein
1 Ribeiro, Celso Carneiro
1 Roditty, Iam
1 Roytman, Alan
1 Schmidt, Jens M.
1 Secher, Jens Peter
1 Sommer, Christian
...and 6 more Co-Authors

Publications by Year

Citations contained in zbMATH Open

136 Publications have been cited 1,683 times in 1,135 Documents Cited by Year
Approximate distance oracles. Zbl 1175.68303
Thorup, Mikkel; Zwick, Uri
212
2005
Deterministic constructions of approximate distance oracles and spanners. Zbl 1082.68087
Roditty, Liam; Thorup, Mikkel; Zwick, Uri
140
2005
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Zbl 1127.68408
Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel
81
2001
Undirected single-source shortest paths with positive integer weights in linear time. Zbl 1065.68597
Thorup, Mikkel
58
1999
Compact oracles for reachability and approximate distances in planar digraphs. Zbl 1125.68394
Thorup, Mikkel
58
2004
Rounding algorithms for a geometric embedding of minimum multiway cut. Zbl 1082.90149
Karger, David R.; Klein, Philip; Stein, Cliff; Thorup, Mikkel; Young, Neal E.
43
2004
Time-space trade-offs for predecessor search. Zbl 1301.68150
Pătraşcu, Mihai; Thorup, Mikkel
39
2006
All structured programs have small tree width and good register allocation. Zbl 0924.68023
Thorup, Mikkel
33
1998
Spanners and emulators with sublinear distance errors. Zbl 1192.05041
Thorup, Mikkel; Zwick, Uri
33
2006
Near-optimal fully-dynamic graph connectivity. Zbl 1296.05110
Thorup, Mikkel
32
2000
Dynamic ordered sets with exponential search trees. Zbl 1292.68038
Andersson, Arne; Thorup, Mikkel
31
2007
A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing. Zbl 1072.90528
Buriol, L. S.; Resende, M. G. C.; Ribeiro, C. C.; Thorup, M.
26
2005
Maintaining information in fully dynamic trees with top trees. Zbl 1321.68211
Alstrup, Stephen; Holm, Jacob; Lichtenberg, Kristian De; Thorup, Mikkel
26
2005
The minimum \(k\)-way cut of bounded size is fixed-parameter tractable. Zbl 1292.68094
Kawarabayashi, Ken-ichi; Thorup, Mikkel
25
2011
Approximate distance oracles. Zbl 1323.05126
Thorup, Mikkel; Zwick, Uri
23
2001
Oracles for distances avoiding a failed node or link. Zbl 1158.05057
Demetrescu, Camil; Thorup, Mikkel; Chowdhury, Rezaul Alam; Ramachandran, Vijaya
22
2008
Dominators in linear time. Zbl 0939.68158
Alstrup, Stephen; Harel, Dov; Lauridsen, Peter W.; Thorup, Mikkel
21
1999
An \(O(n\log n)\) algorithm for the maximum agreement subtree problem for binary trees. Zbl 0976.68081
Cole, Richard; Farach-Colton, Martin; Hariharan, Ramesh; Przytycka, Teresa; Thorup, Mikkel
20
2000
Increasing internet capacity using local search. Zbl 1069.90024
Fortz, Bernard; Thorup, Mikkel
20
2004
Worst-case update times for fully-dynamic all-pairs shortest paths. Zbl 1192.68493
Thorup, Mikkel
20
2005
On the approximability of numerical taxonomy (fitting distances by tree metrics). Zbl 1012.65015
Agarwala, Richa; Bafna, Vineet; Farach, Martin; Paterson, Mike; Thorup, Mikkel
19
1999
Minimum \(k\)-way cuts via deterministic greedy tree packing. Zbl 1231.68185
Thorup, Mikkel
19
2008
OPT versus LOAD in dynamic storage allocation. Zbl 1101.68599
Buchsbaum, Adam L.; Karloff, Howard; Kenyon, Claire; Reingold, Nick; Thorup, Mikkel
18
2004
Changing base without losing space. Zbl 1293.68118
Dodis, Yevgeniy; Patrascu, Mihai; Thorup, Mikkel
17
2010
String matching in Lempel-Ziv compressed strings. Zbl 0899.68046
Farach, M.; Thorup, M.
15
1998
Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles. Zbl 1095.68628
Thorup, Mikkel
15
2004
String matching in Lempel-Ziv compressed strings. Zbl 0978.68520
Farach, Martin; Thorup, Mikkel
15
1995
Integer priority queues with decrease key in constant time and the single source shortest paths problem. Zbl 1084.68030
Thorup, Mikkel
15
2004
Speeding up dynamic shortest-path algorithms. Zbl 1243.90221
Buriol, Luciana S.; Resende, Mauricio G. C.; Thorup, Mikkel
15
2008
On RAM priority queues. Zbl 0968.68037
Thorup, Mikkel
14
2000
Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation. Zbl 1246.68107
Thorup, Mikkel; Zhang, Yin
14
2012
Tight(er) worst-case bounds on dynamic searching and priority queues. Zbl 1296.68038
Andersson, Arne A.; Thorup, Mikkel
14
2000
On the agreement of many trees. Zbl 0875.68693
Farach, Martin; Przytycka, Teresa M.; Thorup, Mikkel
13
1995
Deterministic global minimum cut of a simple graph in near-linear time. Zbl 1321.05268
Kawarabayashi, Ken-ichi; Thorup, Mikkel
13
2015
Regular expression matching with multi-strings and intervals. Zbl 1288.68299
Bille, Philip; Thorup, Mikkel
13
2010
Fusion trees can be implemented with \(AC^0\) instructions only. Zbl 0915.68121
Andersson, Arne; Miltersen, Peter Bro; Thorup, Mikkel
12
1999
Quick \(k\)-median, \(k\)-center, and facility location for sparse graphs. Zbl 1099.68136
Thorup, Mikkel
12
2005
Fast comparison of evolutionary trees. Zbl 0869.92013
Farach, Martin; Thorup, Mikkel
12
1994
Roundtrip spanners and roundtrip routing in directed graphs. Zbl 1093.68627
Roditty, Liam; Thorup, Mikkel; Zwick, Uri
12
2002
Adjacency labeling schemes and induced-universal graphs. Zbl 1321.05226
Alstrup, Stephen; Kaplan, Haim; Thorup, Mikkel; Zwick, Uri
12
2015
On RAM priority queues. Zbl 0848.68024
Thorup, Mikkel
11
1996
Randomized sorting in \(O(n\log\log n)\) time and linear space using addition, shift, and bit-wise Boolean operations. Zbl 1002.68038
Thorup, Mikkel
11
2002
Faster regular expression matching. Zbl 1248.68576
Bille, Philip; Thorup, Mikkel
11
2009
Tabulation based 4-universal hashing with applications to second moment estimation. Zbl 1318.68198
Thorup, Mikkel; Zhang, Yin
11
2004
Integer priority queues with decrease key in constant time and the single source shortest paths problem. Zbl 1192.90048
Thorup, Mikkel
11
2003
Rounding algorithms for a geometric embedding of minimum multiway cut. Zbl 1345.90095
Karger, David R.; Klein, Philip; Stein, Cliff; Thorup, Mikkel; Young, Neal E.
11
1999
Compact name-independent routing with minimum stretch. Zbl 1445.68143
Abraham, Ittai; Gavoille, Cyril; Malkhi, Dahlia; Nisan, Noam; Thorup, Mikkel
11
2008
Maintaining center and median in dynamic trees. Zbl 0966.68510
Alstrup, Stephen; Holm, Jacob; Thorup, Mikkel
10
2000
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Zbl 1028.68221
Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel
10
1998
Survivable IP network design with OSPF routing. Zbl 1131.90319
Buriol, L. S.; Resende, M. G. C.; Thorup, M.
9
2007
Equivalence between priority queues and sorting. Zbl 1326.68113
Thorup, Mikkel
9
2007
On shortcutting digraphs. Zbl 0793.68117
Thorup, Mikkel
9
1993
Construction and impromptu repair of an MST in a distributed network with \(o(m)\) communication. Zbl 1333.68213
King, Valerie; Kutten, Shay; Thorup, Mikkel
9
2015
Floats, integers, and single source shortest paths. Zbl 0951.68025
Thorup, Mikkel
8
2000
On the approximability of numerical taxonomy. (Fitting distances by tree metrics). Zbl 0853.65014
Agarwala, Richa; Bafna, Vineet; Farach, Martin; Narayanan, Babu; Paterson, Mike; Thorup, Mikkel
8
1996
Maximum overhang. Zbl 1229.00005
Paterson, Mike; Peres, Yuval; Thorup, Mikkel; Winkler, Peter; Zwick, Uri
8
2009
Parallel shortcutting of rooted trees. Zbl 0876.68085
Thorup, Mikkel
8
1997
More compact oracles for approximate distances in undirected planar graphs. Zbl 1423.68350
Kawarabayashi, Ken-Ichi; Sommer, Christian; Thorup, Mikkel
8
2013
The power of simple tabulation hashing. Zbl 1281.68089
Pǎtraşcu, Mihai; Thorup, Mikkel
8
2012
Intra-domain traffic engineering with shortest path routing protocols. Zbl 1188.90058
Altın, Ayşegül; Fortz, Bernard; Thorup, Mikkel; Ümit, Hakan
7
2009
Shortcutting planar digraphs. Zbl 0839.05044
Thorup, Mikkel
7
1995
Faster deterministic sorting and priority queues in linear space. Zbl 0929.68025
Thorup, Mikkel
7
1998
Sparse dynamic programming for evolutionary-tree comparison. Zbl 0871.05050
Farach, Martin; Thorup, Mikkel
7
1997
Randomization does not help searching predecessors. Zbl 1302.68102
Pǎtraşcu, Mihai; Thorup, Mikkel
7
2007
Three-in-a-tree in near linear time. Zbl 07298327
Lai, Kai-Yuan; Lu, Hsueh-I.; Thorup, Mikkel
7
2020
Minimizing diameters of dynamic trees. Zbl 1401.68240
Alstrup, Stephen; Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel
7
1997
Roundtrip spanners and roundtrip routing in directed graphs. Zbl 1420.68159
Roditty, Iam; Thorup, Mikkel; Zwick, Uri
7
2008
Adjacency labeling schemes and induced-universal graphs. Zbl 1403.05123
Alstrup, Stephen; Kaplan, Haim; Thorup, Mikkel; Zwick, Uri
7
2019
Decremental dynamic connectivity. Zbl 0957.68091
Thorup, Mikkel
6
1999
Quick \(k\)-median, \(k\)-center, and facility location for sparse graphs. Zbl 0986.90067
Thorup, Mikkel
6
2001
Coloring 3-colorable graphs with less than \(n^{1/5}\) colors. Zbl 1426.05166
Kawarabayashi, Ken-Ichi; Thorup, Mikkel
6
2017
Even strongly universal hashing is pretty fast. Zbl 0956.68509
Thorup, Mikkel
5
2000
Faster worst case deterministic dynamic connectivity. Zbl 1397.68142
Kejlberg-Rasmussen, Casper; Kopelowitz, Tsvi; Pettie, Seth; Thorup, Mikkel
5
2016
On \(\text{AC}^0\) implementations of fusion trees and atomic heaps. Zbl 1092.68633
Thorup, Mikkel
5
2003
Bottom-\(k\) and priority sampling, set similarity and subset sums with minimal independence. Zbl 1293.68107
Thorup, Mikkel
5
2013
Black box for constant-time insertion in priority queues (note). Zbl 1321.68232
Alstrup, Stephen; Husfeldt, Thore; Rauhe, Theis; Thorup, Mikkel
5
2005
Deterministic edge connectivity in near-linear time. Zbl 1426.68217
Kawarabayashi, Ken-Ichi; Thorup, Mikkel
5
2019
The power of simple tabulation hashing. Zbl 1288.68056
Patrascu, Mihai; Thorup, Mikkel
5
2011
Finding cores of limited length. Zbl 1517.68270
Alstrup, Stephen; Lauridsen, Peter W.; Sommerlund, Peer; Thorup, Mikkel
5
1997
On the \(k\)-independence required by linear probing and minwise independence. Zbl 1398.68118
Pǎtraşcu, Mihai; Thorup, Mikkel
5
2016
Optimal pointer algorithms for finding nearest common ancestors in dynamic trees. Zbl 0951.68180
Alstrup, Stephen; Thorup, Mikkel
4
2000
Sampling to provide or to bound: With applications to fully dynamic graph algorithms. Zbl 0888.68065
Henzinger, Monika R.; Thorup, Mikkel
4
1997
Dynamic graph algorithms with applications. Zbl 0966.68605
Thorup, Mikkel; Karger, David R.
4
2000
Priority sampling for estimation of arbitrary subset sums. Zbl 1326.68036
Duffield, Nick G.; Lund, Carsten; Thorup, Mikkel
4
2007
Coloring 3-colorable graphs with \(o(n^{1/5})\) colors. Zbl 1359.05123
Kawarabayashi, Ken-ichi; Thorup, Mikkel
4
2014
Faster algorithms for edge connectivity via random 2-out contractions. Zbl 07304100
Ghaffari, Mohsen; Nowicki, Krzysztof; Thorup, Mikkel
4
2020
Space efficient dynamic stabbing with fast queries. Zbl 1192.68143
Thorup, Mikkel
4
2003
Fast fencing. Zbl 1427.68323
Abrahamsen, Mikkel; Adamaszek, Anna; Bringmann, Karl; Cohen-Addad, Vincent; Mehr, Mehran; Rotenberg, Eva; Roytman, Alan; Thorup, Mikkel
4
2018
Efficient stream sampling for variance-optimal estimation of subset sums. Zbl 1231.62010
Cohen, Edith; Duffield, Nick; Kaplan, Haim; Lund, Carsten; Thorup, Mikkel
3
2011
Structured programs have small tree-width and good register allocation. (Extended abstract). Zbl 0890.68035
Thorup, Mikkel
3
1997
Quick and good facility location. Zbl 1094.68123
Thorup, Mikkel
3
2003
Union-find with constant time deletions. Zbl 1084.68026
Alstrup, Stephen; Gørtz, Inge Li; Rauhe, Theis; Thorup, Mikkel; Zwick, Uri
3
2005
Fast comparison of evolutionary trees. Zbl 1096.92501
Farach, Martin; Thorup, Mikkel
3
1995
An experimental study of poly-logarithmic fully-dynamic connectivity algorithms. Zbl 1085.68743
Iyer, Raj D. jun.; Karger, David; Rahul, Hariharan S.; Thorup, Mikkel
3
2001
Oracles for distances avoiding a link-failure. Zbl 1093.68614
Demetrescu, Camil; Thorup, Mikkel
3
2002
From independence to expansion and back again. Zbl 1321.68219
Christiani, Tobias; Pagh, Rasmus; Thorup, Mikkel
3
2015
A space saving trick for directed dynamic transitive closure and shortest path algorithms. Zbl 0996.68526
King, Valerie; Thorup, Mikkel
3
2001
Stream sampling for variance-optimal estimation of subset sums. Zbl 1426.62024
Cohen, Edith; Duffield, Nick; Kaplan, Haim; Lund, Carsten; Thorup, Mikkel
3
2009
On the \(k\)-independence required by linear probing and minwise independence. Zbl 1288.68050
Pǎtraşcu, Mihai; Thorup, Mikkel
3
2010
Mihai Pǎtraşcu: obituary and open problems. Zbl 1395.01075
Thorup, Mikkel
3
2013
Compact cactus representations of all non-trivial min-cuts. Zbl 1472.05085
Lo, On-Hei S.; Schmidt, Jens M.; Thorup, Mikkel
2
2021
Load balancing with dynamic set of balls and bins. Zbl 07765247
Aamand, Anders; Knudsen, Jakob Bæk Tejs; Thorup, Mikkel
1
2021
Three-in-a-tree in near linear time. Zbl 07298327
Lai, Kai-Yuan; Lu, Hsueh-I.; Thorup, Mikkel
7
2020
Faster algorithms for edge connectivity via random 2-out contractions. Zbl 07304100
Ghaffari, Mohsen; Nowicki, Krzysztof; Thorup, Mikkel
4
2020
Disks in curves of bounded convex curvature. Zbl 1445.51004
Aamand, Anders; Abrahamsen, Mikkel; Thorup, Mikkel
2
2020
Adjacency labeling schemes and induced-universal graphs. Zbl 1403.05123
Alstrup, Stephen; Kaplan, Haim; Thorup, Mikkel; Zwick, Uri
7
2019
Deterministic edge connectivity in near-linear time. Zbl 1426.68217
Kawarabayashi, Ken-Ichi; Thorup, Mikkel
5
2019
Fast fencing. Zbl 1427.68323
Abrahamsen, Mikkel; Adamaszek, Anna; Bringmann, Karl; Cohen-Addad, Vincent; Mehr, Mehran; Rotenberg, Eva; Roytman, Alan; Thorup, Mikkel
4
2018
Power of \(d\) choices with simple tabulation. Zbl 1499.68038
Aamand, Anders; Knudsen, Mathias Bæk Tejs; Thorup, Mikkel
3
2018
Incremental exact min-cut in polylogarithmic amortized update time. Zbl 1454.68103
Goranci, Gramoz; Henzinger, Monika; Thorup, Mikkel
3
2018
Consistent hashing with bounded loads. Zbl 1403.68022
Mirrokni, Vahab; Thorup, Mikkel; Zadimoghaddam, Morteza
1
2018
Coloring 3-colorable graphs with less than \(n^{1/5}\) colors. Zbl 1426.05166
Kawarabayashi, Ken-Ichi; Thorup, Mikkel
6
2017
Faster worst case deterministic dynamic connectivity. Zbl 1397.68142
Kejlberg-Rasmussen, Casper; Kopelowitz, Tsvi; Pettie, Seth; Thorup, Mikkel
5
2016
On the \(k\)-independence required by linear probing and minwise independence. Zbl 1398.68118
Pǎtraşcu, Mihai; Thorup, Mikkel
5
2016
The power of two choices with simple tabulation. Zbl 1410.68067
Dahlgaard, Søren; Knudsen, Mathias Bæk Tejs; Rotenberg, Eva; Thorup, Mikkel
3
2016
Finding the maximum subset with bounded convex curvature. Zbl 1387.68224
Abrahamsen, Mikkel; Thorup, Mikkel
2
2016
Incremental exact min-cut in poly-logarithmic amortized update time. Zbl 1397.68099
Goranci, Gramoz; Henzinger, Monika; Thorup, Mikkel
1
2016
Bottleneck paths and trees and deterministic graphical games. Zbl 1388.68109
Chechik, Shiri; Kaplan, Haim; Thorup, Mikkel; Zamir, Or; Zwick, Uri
1
2016
Deterministic global minimum cut of a simple graph in near-linear time. Zbl 1321.05268
Kawarabayashi, Ken-ichi; Thorup, Mikkel
13
2015
Adjacency labeling schemes and induced-universal graphs. Zbl 1321.05226
Alstrup, Stephen; Kaplan, Haim; Thorup, Mikkel; Zwick, Uri
12
2015
Construction and impromptu repair of an MST in a distributed network with \(o(m)\) communication. Zbl 1333.68213
King, Valerie; Kutten, Shay; Thorup, Mikkel
9
2015
From independence to expansion and back again. Zbl 1321.68219
Christiani, Tobias; Pagh, Rasmus; Thorup, Mikkel
3
2015
RAM-efficient external memory sorting. Zbl 1331.68067
Arge, Lars; Thorup, Mikkel
1
2015
Coloring 3-colorable graphs with \(o(n^{1/5})\) colors. Zbl 1359.05123
Kawarabayashi, Ken-ichi; Thorup, Mikkel
4
2014
Approximately minwise independence with twisted tabulation. Zbl 1417.68037
Dahlgaard, Søren; Thorup, Mikkel
2
2014
Algorithms and estimators for summarization of unaggregated data streams. Zbl 1311.68010
Cohen, Edith; Duffield, Nick; Kaplan, Haim; Lund, Carstent; Thorup, Mikkel
2
2014
Union-find with constant time deletions. Zbl 1398.68101
Alstrup, Stephen; Thorup, Mikkel; Gørtz, Inge Li; Rauhe, Theis; Zwick, Uri
2
2014
More compact oracles for approximate distances in undirected planar graphs. Zbl 1423.68350
Kawarabayashi, Ken-Ichi; Sommer, Christian; Thorup, Mikkel
8
2013
Bottom-\(k\) and priority sampling, set similarity and subset sums with minimal independence. Zbl 1293.68107
Thorup, Mikkel
5
2013
Mihai Pǎtraşcu: obituary and open problems. Zbl 1395.01075
Thorup, Mikkel
3
2013
Intra-domain traffic engineering with shortest path routing protocols. Zbl 1269.90121
Altın, Ayşegül; Fortz, Bernard; Thorup, Mikkel; Ümit, Hakan
1
2013
RAM-efficient external memory sorting. Zbl 1329.68089
Arge, Lars; Thorup, Mikkel
1
2013
Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation. Zbl 1246.68107
Thorup, Mikkel; Zhang, Yin
14
2012
The power of simple tabulation hashing. Zbl 1281.68089
Pǎtraşcu, Mihai; Thorup, Mikkel
8
2012
The minimum \(k\)-way cut of bounded size is fixed-parameter tractable. Zbl 1292.68094
Kawarabayashi, Ken-ichi; Thorup, Mikkel
25
2011
The power of simple tabulation hashing. Zbl 1288.68056
Patrascu, Mihai; Thorup, Mikkel
5
2011
Efficient stream sampling for variance-optimal estimation of subset sums. Zbl 1231.62010
Cohen, Edith; Duffield, Nick; Kaplan, Haim; Lund, Carsten; Thorup, Mikkel
3
2011
Don’t rush into a union, take time to find your roots. Zbl 1288.68134
Pătraşcu, Mihai; Thorup, Mikkel
1
2011
Changing base without losing space. Zbl 1293.68118
Dodis, Yevgeniy; Patrascu, Mihai; Thorup, Mikkel
17
2010
Regular expression matching with multi-strings and intervals. Zbl 1288.68299
Bille, Philip; Thorup, Mikkel
13
2010
On the \(k\)-independence required by linear probing and minwise independence. Zbl 1288.68050
Pǎtraşcu, Mihai; Thorup, Mikkel
3
2010
Discounted deterministic Markov decision processes and discounted all-pairs shortest paths. Zbl 1300.05303
Madani, Omid; Thorup, Mikkel; Zwick, Uri
2
2010
Faster regular expression matching. Zbl 1248.68576
Bille, Philip; Thorup, Mikkel
11
2009
Maximum overhang. Zbl 1229.00005
Paterson, Mike; Peres, Yuval; Thorup, Mikkel; Winkler, Peter; Zwick, Uri
8
2009
Intra-domain traffic engineering with shortest path routing protocols. Zbl 1188.90058
Altın, Ayşegül; Fortz, Bernard; Thorup, Mikkel; Ümit, Hakan
7
2009
Stream sampling for variance-optimal estimation of subset sums. Zbl 1426.62024
Cohen, Edith; Duffield, Nick; Kaplan, Haim; Lund, Carsten; Thorup, Mikkel
3
2009
Higher lower bounds for near-neighbor and further rich problems. Zbl 1200.68081
Pătraşcu, Mihai; Thorup, Mikkel
1
2009
String hashing for linear probing. Zbl 1422.68055
Thorup, Mikkel
1
2009
Oracles for distances avoiding a failed node or link. Zbl 1158.05057
Demetrescu, Camil; Thorup, Mikkel; Chowdhury, Rezaul Alam; Ramachandran, Vijaya
22
2008
Minimum \(k\)-way cuts via deterministic greedy tree packing. Zbl 1231.68185
Thorup, Mikkel
19
2008
Speeding up dynamic shortest-path algorithms. Zbl 1243.90221
Buriol, Luciana S.; Resende, Mauricio G. C.; Thorup, Mikkel
15
2008
Compact name-independent routing with minimum stretch. Zbl 1445.68143
Abraham, Ittai; Gavoille, Cyril; Malkhi, Dahlia; Nisan, Noam; Thorup, Mikkel
11
2008
Roundtrip spanners and roundtrip routing in directed graphs. Zbl 1420.68159
Roditty, Iam; Thorup, Mikkel; Zwick, Uri
7
2008
Dynamic ordered sets with exponential search trees. Zbl 1292.68038
Andersson, Arne; Thorup, Mikkel
31
2007
Survivable IP network design with OSPF routing. Zbl 1131.90319
Buriol, L. S.; Resende, M. G. C.; Thorup, M.
9
2007
Equivalence between priority queues and sorting. Zbl 1326.68113
Thorup, Mikkel
9
2007
Randomization does not help searching predecessors. Zbl 1302.68102
Pǎtraşcu, Mihai; Thorup, Mikkel
7
2007
Priority sampling for estimation of arbitrary subset sums. Zbl 1326.68036
Duffield, Nick G.; Lund, Carsten; Thorup, Mikkel
4
2007
On the variance of subset sum estimation. Zbl 1151.68395
Szegedy, Mario; Thorup, Mikkel
1
2007
Time-space trade-offs for predecessor search. Zbl 1301.68150
Pătraşcu, Mihai; Thorup, Mikkel
39
2006
Spanners and emulators with sublinear distance errors. Zbl 1192.05041
Thorup, Mikkel; Zwick, Uri
33
2006
Does path cleaning help in dynamic all-pairs shortest paths? Zbl 1131.90454
Demetrescu, C.; Faruolo, P.; Italiano, G. F.; Thorup, M.
1
2006
Melding priority queues. Zbl 1321.68228
Mendelson, Ran; Tarjan, Robert E.; Thorup, Mikkel; Zwick, Uri
1
2006
Approximate distance oracles. Zbl 1175.68303
Thorup, Mikkel; Zwick, Uri
212
2005
Deterministic constructions of approximate distance oracles and spanners. Zbl 1082.68087
Roditty, Liam; Thorup, Mikkel; Zwick, Uri
140
2005
A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing. Zbl 1072.90528
Buriol, L. S.; Resende, M. G. C.; Ribeiro, C. C.; Thorup, M.
26
2005
Maintaining information in fully dynamic trees with top trees. Zbl 1321.68211
Alstrup, Stephen; Holm, Jacob; Lichtenberg, Kristian De; Thorup, Mikkel
26
2005
Worst-case update times for fully-dynamic all-pairs shortest paths. Zbl 1192.68493
Thorup, Mikkel
20
2005
Quick \(k\)-median, \(k\)-center, and facility location for sparse graphs. Zbl 1099.68136
Thorup, Mikkel
12
2005
Black box for constant-time insertion in priority queues (note). Zbl 1321.68232
Alstrup, Stephen; Husfeldt, Thore; Rauhe, Theis; Thorup, Mikkel
5
2005
Union-find with constant time deletions. Zbl 1084.68026
Alstrup, Stephen; Gørtz, Inge Li; Rauhe, Theis; Thorup, Mikkel; Zwick, Uri
3
2005
Learn more, sample less: control of volume and variance in network measurement. Zbl 1296.94015
Duffield, Nick; Lund, Carsten; Thorup, Mikkel
2
2005
Compact oracles for reachability and approximate distances in planar digraphs. Zbl 1125.68394
Thorup, Mikkel
58
2004
Rounding algorithms for a geometric embedding of minimum multiway cut. Zbl 1082.90149
Karger, David R.; Klein, Philip; Stein, Cliff; Thorup, Mikkel; Young, Neal E.
43
2004
Increasing internet capacity using local search. Zbl 1069.90024
Fortz, Bernard; Thorup, Mikkel
20
2004
OPT versus LOAD in dynamic storage allocation. Zbl 1101.68599
Buchsbaum, Adam L.; Karloff, Howard; Kenyon, Claire; Reingold, Nick; Thorup, Mikkel
18
2004
Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles. Zbl 1095.68628
Thorup, Mikkel
15
2004
Integer priority queues with decrease key in constant time and the single source shortest paths problem. Zbl 1084.68030
Thorup, Mikkel
15
2004
Tabulation based 4-universal hashing with applications to second moment estimation. Zbl 1318.68198
Thorup, Mikkel; Zhang, Yin
11
2004
Melding priority queues. Zbl 1095.68577
Mendelson, Ran; Tarjan, Robert E.; Thorup, Mikkel; Zwick, Uri
2
2004
On adaptive integer sorting. Zbl 1111.68413
Pagh, Anna; Pagh, Rasmus; Thorup, Mikkel
1
2004
Integer priority queues with decrease key in constant time and the single source shortest paths problem. Zbl 1192.90048
Thorup, Mikkel
11
2003
On \(\text{AC}^0\) implementations of fusion trees and atomic heaps. Zbl 1092.68633
Thorup, Mikkel
5
2003
Space efficient dynamic stabbing with fast queries. Zbl 1192.68143
Thorup, Mikkel
4
2003
Quick and good facility location. Zbl 1094.68123
Thorup, Mikkel
3
2003
OPT versus LOAD in dynamic storage allocation. Zbl 1192.68311
Buchsbaum, Adam L.; Karloff, Howard; Kenyon, Claire; Reingold, Nick; Thorup, Mikkel
1
2003
Roundtrip spanners and roundtrip routing in directed graphs. Zbl 1093.68627
Roditty, Liam; Thorup, Mikkel; Zwick, Uri
12
2002
Randomized sorting in \(O(n\log\log n)\) time and linear space using addition, shift, and bit-wise Boolean operations. Zbl 1002.68038
Thorup, Mikkel
11
2002
Oracles for distances avoiding a link-failure. Zbl 1093.68614
Demetrescu, Camil; Thorup, Mikkel
3
2002
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Zbl 1127.68408
Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel
81
2001
Approximate distance oracles. Zbl 1323.05126
Thorup, Mikkel; Zwick, Uri
23
2001
Quick \(k\)-median, \(k\)-center, and facility location for sparse graphs. Zbl 0986.90067
Thorup, Mikkel
6
2001
An experimental study of poly-logarithmic fully-dynamic connectivity algorithms. Zbl 1085.68743
Iyer, Raj D. jun.; Karger, David; Rahul, Hariharan S.; Thorup, Mikkel
3
2001
A space saving trick for directed dynamic transitive closure and shortest path algorithms. Zbl 0996.68526
King, Valerie; Thorup, Mikkel
3
2001
Fully-dynamic MIN-cut. Zbl 1323.68322
Thorup, Mikkel
2
2001
Dynamic string searching. Zbl 0987.68022
Andersson, Arne; Thorup, Mikkel
1
2001
Near-optimal fully-dynamic graph connectivity. Zbl 1296.05110
Thorup, Mikkel
32
2000
An \(O(n\log n)\) algorithm for the maximum agreement subtree problem for binary trees. Zbl 0976.68081
Cole, Richard; Farach-Colton, Martin; Hariharan, Ramesh; Przytycka, Teresa; Thorup, Mikkel
20
2000
On RAM priority queues. Zbl 0968.68037
Thorup, Mikkel
14
2000
Tight(er) worst-case bounds on dynamic searching and priority queues. Zbl 1296.68038
Andersson, Arne A.; Thorup, Mikkel
14
2000
...and 36 more Documents
all top 5

Cited by 1,769 Authors

22 Thorup, Mikkel
20 Bille, Philip
18 Gawrychowski, Paweł
18 Italiano, Giuseppe Francesco
18 Roditty, Liam
17 Navarro, Gonzalo
17 Neiman, Ofer
16 Baswana, Surender
16 Gørtz, Inge Li
14 Rauch Henzinger, Monika
13 Gavoille, Cyril
13 Georgiadis, Loukas
12 Saurabh, Saket
12 Weimann, Oren
11 Chan, Timothy Moon-Yew
11 Dragan, Feodor F.
11 Elkin, Michael
11 Mulzer, Wolfgang Johann Heinrich
11 Nekrich, Yakov
11 Resende, Mauricio G. C.
10 Chandrasekaran, Karthekeyan
10 Filtser, Arnold
10 Fomin, Fedor V.
10 Mozes, Shay
10 Proietti, Guido
9 Alstrup, Stephen
9 Chepoi, Victor D.
9 Fortz, Bernard
9 Golovach, Petr A.
9 Kaplan, Haim
9 Pelc, Andrzej
9 Peleg, David
9 Pettie, Seth
8 Kavitha, Telikepalli
8 Leucci, Stefano
8 Munro, J. Ian
8 Sadakane, Kunihiko
8 Seiferth, Paul
7 Bilò, Davide
7 Demaine, Erik D.
7 Hagerup, Torben
7 Lokshtanov, Daniel
7 Pilipczuk, Marcin L.
7 Porat, Ely
7 Raman, Venkatesh
7 Rytter, Wojciech
7 Satti, Srinivasa Rao
7 Xu, Chao
7 Zhang, Peng
6 Abraham, Ittai
6 Abrahamsen, Mikkel
6 Amir, Amihood
6 Censor-Hillel, Keren
6 Chakraborty, Sankardeep
6 Chekuri, Chandra S.
6 Elmasry, Amr
6 Grabowski, Szymon
6 Gualà, Luciano
6 Korman, Amos
6 Landau, Gad M.
6 Levy, Avivit
6 Nanongkai, Danupon
6 Parotsidis, Nikos
6 Raman, Rajeev
6 Stølting Brodal, Gerth
6 Sung, Wing-Kin
6 Tsichlas, Kostas
6 Wulff-Nilsen, Christian
6 Xiao, Mingyu
6 Zwick, Uri
5 Abboud, Amir
5 Alon, Noga
5 Bley, Andreas
5 Chechik, Shiri
5 Choudhary, Keerti
5 Ducoffe, Guillaume
5 Gagie, Travis
5 Gupta, Anupam
5 Jansson, Jesper
5 Katajainen, Jyrki
5 Kawarabayashi, Ken-ichi
5 King, Valerie
5 Klein, Philip N.
5 Naor, Assaf
5 Nelson, Jelani
5 Pilipczuk, Michał
5 Sen, Sandeep
5 Shalom, B. Riva
5 Sharma, Roohani
5 Sohler, Christian
5 Tsakalidis, Konstantinos
5 ümit, Hakan
5 Vassilevska Williams, Virginia
5 Wahlström, Magnus
4 Ausiello, Giorgio
4 Bartal, Yair
4 Bérczi, Kristóf
4 Bernstein, Aaron
4 Berry, Vincent
4 Bose, Prosenjit K.
...and 1,669 more Authors
all top 5

Cited in 124 Serials

117 Algorithmica
109 Theoretical Computer Science
50 Discrete Applied Mathematics
45 SIAM Journal on Computing
35 Information Processing Letters
35 Journal of Computer and System Sciences
28 SIAM Journal on Discrete Mathematics
24 Information and Computation
23 Journal of Discrete Algorithms
22 Theory of Computing Systems
19 Distributed Computing
13 Computers & Operations Research
13 Computational Geometry
11 Networks
11 Discrete & Computational Geometry
11 Mathematical Programming. Series A. Series B
10 European Journal of Operational Research
10 Journal of Combinatorial Optimization
9 Annals of Operations Research
9 Journal of Graph Algorithms and Applications
7 International Transactions in Operational Research
7 Computer Science Review
6 Discrete Mathematics
6 International Journal of Foundations of Computer Science
6 ACM Journal of Experimental Algorithmics
4 American Mathematical Monthly
4 Applied Mathematics and Computation
4 Computing
4 Combinatorica
3 Acta Informatica
3 Artificial Intelligence
3 Mathematics of Operations Research
3 European Journal of Combinatorics
3 Operations Research Letters
3 Journal of Cryptology
3 Random Structures & Algorithms
3 Linear Algebra and its Applications
3 Discrete Optimization
3 Optimization Letters
3 Algorithms
2 Israel Journal of Mathematics
2 Nuclear Physics. B
2 Information Sciences
2 Journal of Combinatorial Theory. Series B
2 Operations Research
2 Results in Mathematics
2 Journal of Automated Reasoning
2 Cybernetics and Systems Analysis
2 Computational Optimization and Applications
2 Top
2 Constraints
2 INFORMS Journal on Computing
2 Journal of the ACM
2 Journal of Machine Learning Research (JMLR)
2 ACM Transactions on Algorithms
1 ACM Computing Surveys
1 Computers & Mathematics with Applications
1 Communications in Mathematical Physics
1 Journal of Mathematical Biology
1 Journal of Statistical Physics
1 Mathematical Proceedings of the Cambridge Philosophical Society
1 Physics Reports
1 ACM Transactions on Database Systems
1 Mathematics Magazine
1 Advances in Mathematics
1 The Annals of Statistics
1 Biometrical Journal
1 Bulletin of the London Mathematical Society
1 Inventiones Mathematicae
1 Journal of Combinatorial Theory. Series A
1 Journal of Graph Theory
1 Journal of Mathematical Psychology
1 Journal of Classification
1 Graphs and Combinatorics
1 Probability Theory and Related Fields
1 Statistical Science
1 Asia-Pacific Journal of Operational Research
1 Journal of Parallel and Distributed Computing
1 Real-Time Systems
1 The Annals of Applied Probability
1 MSCS. Mathematical Structures in Computer Science
1 Acta Mathematica Universitatis Comenianae. New Series
1 Journal of Global Optimization
1 Geometric and Functional Analysis. GAFA
1 Pattern Recognition
1 Journal of Knot Theory and its Ramifications
1 Journal of Mathematical Imaging and Vision
1 Formal Methods in System Design
1 Advances in Applied Clifford Algebras
1 The Electronic Journal of Combinatorics
1 Journal of Functional Programming
1 Electronic Communications in Probability
1 Journal of Heuristics
1 Mathematical Problems in Engineering
1 Optimization Methods & Software
1 Mathematical Methods of Operations Research
1 Chicago Journal of Theoretical Computer Science
1 Journal of Scheduling
1 Data Mining and Knowledge Discovery
1 Journal of the European Mathematical Society (JEMS)
...and 24 more Serials

Citations by Year

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.