×

zbMATH — the first resource for mathematics

Thorup, Mikkel

Compute Distance To:
Author ID: thorup.mikkel Recent zbMATH articles by "Thorup, Mikkel"
Published as: Thorup, M.; Thorup, Mikkel
External Links: MGP · Wikidata · dblp · GND
Documents Indexed: 146 Publications since 1991
all top 5

Co-Authors

37 single-authored
18 Zwick, Uri
13 Alstrup, Stephen
10 Patrascu, Mihai
8 Farach, Martin
7 Holm, Jacob
6 Kaplan, Haim
6 Kawarabayashi, Ken-ichi
5 de Lichtenberg, Kristian
5 Duffield, Nick G.
4 Andersson, Arne A.
4 Karger, David R.
4 Lund, Carsten
4 Paterson, Mike S.
4 Rauch Henzinger, Monika
3 Aamand, Anders
3 Abrahamsen, Mikkel
3 Buriol, Luciana S.
3 Cohen, Edith
3 Demetrescu, Camil
3 Fortz, Bernard
3 Knudsen, Mathias Bæk Tejs
3 Mendelson, Ran
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 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 Lauridsen, Peter W.
2 Madani, Omid
2 Pagh, Rasmus
2 Peres, Yuval
2 Przytycka, Teresa M.
2 Reingold, Nick
2 Roditty, Liam
2 Stein, Clifford
2 Tarjan, Robert Endre
2 ümit, Hakan
2 Winkler, Peter M.
2 Young, Neal E.
1 Abraham, Ittai
1 Adamaszek, Anna
1 Blikle, Andrzej Jacek
1 Bringmann, Karl
1 Bro Miltersen, Peter
1 Chechik, Shiri
1 Chowdhury, Rezaul Alam
1 Christiani, Tobias
1 Cohen-Addad, Vincent
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 Husfeldt, Thore
1 Italiano, Giuseppe Francesco
1 Iyer, Raj D. jun.
1 Kejlberg-Rasmussen, Casper
1 Knudsen, Jakob Bæk Tejs
1 Kopelowitz, Tsvi
1 Kutten, Shay
1 Lai, Kai-Yuan
1 Lu, Hsueh-I
1 Lund, Carstent
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 Secher, Jens Peter
1 Sommer, Christian
1 Szegedy, Mario
1 Tarlecki, Andrzej
1 Zadimoghaddam, Morteza
1 Zamir, Or

Publications by Year

Citations contained in zbMATH

119 Publications have been cited 1,224 times in 808 Documents Cited by Year
Approximate distance oracles. Zbl 1175.68303
Thorup, Mikkel; Zwick, Uri
168
2005
Deterministic constructions of approximate distance oracles and spanners. Zbl 1082.68087
Roditty, Liam; Thorup, Mikkel; Zwick, Uri
125
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
52
2001
Compact oracles for reachability and approximate distances in planar digraphs. Zbl 1125.68394
Thorup, Mikkel
44
2004
Undirected single-source shortest paths with positive integer weights in linear time. Zbl 1065.68597
Thorup, Mikkel
41
1999
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.
33
2004
Time-space trade-offs for predecessor search. Zbl 1301.68150
Pătraşcu, Mihai; Thorup, Mikkel
27
2006
Dynamic ordered sets with exponential search trees. Zbl 1292.68038
Andersson, Arne; Thorup, Mikkel
22
2007
Maintaining information in fully dynamic trees with top trees. Zbl 1321.68211
Alstrup, Stephen; Holm, Jacob; Lichtenberg, Kristian De; Thorup, Mikkel
22
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.
22
2005
Near-optimal fully-dynamic graph connectivity. Zbl 1296.05110
Thorup, Mikkel
22
2000
Spanners and emulators with sublinear distance errors. Zbl 1192.05041
Thorup, Mikkel; Zwick, Uri
21
2006
All structured programs have small tree width and good register allocation. Zbl 0924.68023
Thorup, Mikkel
20
1998
Approximate distance oracles. Zbl 1323.05126
Thorup, Mikkel; Zwick, Uri
17
2001
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
17
2000
On the approximability of numerical taxonomy (fitting distances by tree metrics). Zbl 1012.65015
Agarwala, Richa; Bafna, Vineet; Farach, Martin; Paterson, Mike; Thorup, Mikkel
17
1999
The minimum \(k\)-way cut of bounded size is fixed-parameter tractable. Zbl 1292.68094
Kawarabayashi, Ken-ichi; Thorup, Mikkel
15
2011
OPT versus LOAD in dynamic storage allocation. Zbl 1101.68599
Buchsbaum, Adam L.; Karloff, Howard; Kenyon, Claire; Reingold, Nick; Thorup, Mikkel
15
2004
Increasing internet capacity using local search. Zbl 1069.90024
Fortz, Bernard; Thorup, Mikkel
15
2004
Dominators in linear time. Zbl 0939.68158
Alstrup, Stephen; Harel, Dov; Lauridsen, Peter W.; Thorup, Mikkel
15
1999
String matching in Lempel-Ziv compressed strings. Zbl 0899.68046
Farach, M.; Thorup, M.
15
1998
Oracles for distances avoiding a failed node or link. Zbl 1158.05057
Demetrescu, Camil; Thorup, Mikkel; Chowdhury, Rezaul Alam; Ramachandran, Vijaya
14
2008
Worst-case update times for fully-dynamic all-pairs shortest paths. Zbl 1192.68493
Thorup, Mikkel
14
2005
On the agreement of many trees. Zbl 0875.68693
Farach, Martin; Przytycka, Teresa M.; Thorup, Mikkel
14
1995
On RAM priority queues. Zbl 0968.68037
Thorup, Mikkel
13
2000
Compact name-independent routing with minimum stretch. Zbl 1445.68143
Abraham, Ittai; Gavoille, Cyril; Malkhi, Dahlia; Nisan, Noam; Thorup, Mikkel
12
2008
Minimum \(k\)-way cuts via deterministic greedy tree packing. Zbl 1231.68185
Thorup, Mikkel
12
2008
Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles. Zbl 1095.68628
Thorup, Mikkel
12
2004
Tight(er) worst-case bounds on dynamic searching and priority queues. Zbl 1296.68038
Andersson, Arne A.; Thorup, Mikkel
12
2000
String matching in Lempel-Ziv compressed strings. Zbl 0978.68520
Farach, Martin; Thorup, Mikkel
12
1995
Speeding up dynamic shortest-path algorithms. Zbl 1243.90221
Buriol, Luciana S.; Resende, Mauricio G. C.; Thorup, Mikkel
11
2008
Integer priority queues with decrease key in constant time and the single source shortest paths problem. Zbl 1084.68030
Thorup, Mikkel
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
Roundtrip spanners and roundtrip routing in directed graphs. Zbl 1093.68627
Roditty, Liam; Thorup, Mikkel; Zwick, Uri
11
2002
Fusion trees can be implemented with \(AC^0\) instructions only. Zbl 0915.68121
Andersson, Arne; Miltersen, Peter Bro; Thorup, Mikkel
11
1999
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.
10
1999
Regular expression matching with multi-strings and intervals. Zbl 1288.68299
Bille, Philip; Thorup, Mikkel
9
2010
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
9
1998
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
9
1996
Fast comparison of evolutionary trees. Zbl 0869.92013
Farach, Martin; Thorup, Mikkel
9
1994
Changing base without losing space. Zbl 1293.68118
Dodis, Yevgeniy; Patrascu, Mihai; Thorup, Mikkel
8
2010
Equivalence between priority queues and sorting. Zbl 1326.68113
Thorup, Mikkel
8
2007
Survivable IP network design with OSPF routing. Zbl 1131.90319
Buriol, L. S.; Resende, M. G. C.; Thorup, M.
8
2007
Tabulation based 4-universal hashing with applications to second moment estimation. Zbl 1318.68198
Thorup, Mikkel; Zhang, Yin
8
2004
Maintaining center and median in dynamic trees. Zbl 0966.68510
Alstrup, Stephen; Holm, Jacob; Thorup, Mikkel
8
2000
Floats, integers, and single source shortest paths. Zbl 0951.68025
Thorup, Mikkel
8
2000
Sparse dynamic programming for evolutionary-tree comparison. Zbl 0871.05050
Farach, Martin; Thorup, Mikkel
8
1997
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
Faster deterministic sorting and priority queues in linear space. Zbl 0929.68025
Thorup, Mikkel
7
1998
On shortcutting digraphs. Zbl 0793.68117
Thorup, Mikkel
7
1993
The power of simple tabulation hashing. Zbl 1281.68089
Pǎtraşcu, Mihai; Thorup, Mikkel
6
2012
Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation. Zbl 1246.68107
Thorup, Mikkel; Zhang, Yin
6
2012
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
6
2002
Quick \(k\)-median, \(k\)-center, and facility location for sparse graphs. Zbl 0986.90067
Thorup, Mikkel
6
2001
On RAM priority queues. Zbl 0848.68024
Thorup, Mikkel
6
1996
Deterministic global minimum cut of a simple graph in near-linear time. Zbl 1321.05268
Kawarabayashi, Ken-ichi; Thorup, Mikkel
5
2015
Adjacency labeling schemes and induced-universal graphs. Zbl 1321.05226
Alstrup, Stephen; Kaplan, Haim; Thorup, Mikkel; Zwick, Uri
5
2015
Bottom-\(k\) and priority sampling, set similarity and subset sums with minimal independence. Zbl 1293.68107
Thorup, Mikkel
5
2013
Faster regular expression matching. Zbl 1248.68576
Bille, Philip; Thorup, Mikkel
5
2009
Quick \(k\)-median, \(k\)-center, and facility location for sparse graphs. Zbl 1099.68136
Thorup, Mikkel
5
2005
On \(\text{AC}^0\) implementations of fusion trees and atomic heaps. Zbl 1092.68633
Thorup, Mikkel
5
2003
Minimizing diameters of dynamic trees. Zbl 1401.68240
Alstrup, Stephen; Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel
5
1997
Parallel shortcutting of rooted trees. Zbl 0876.68085
Thorup, Mikkel
5
1997
Shortcutting planar digraphs. Zbl 0839.05044
Thorup, Mikkel
5
1995
Coloring 3-colorable graphs with \(o(n^{1/5})\) colors. Zbl 1359.05123
Kawarabayashi, Ken-ichi; Thorup, Mikkel
4
2014
The power of simple tabulation hashing. Zbl 1288.68056
Patrascu, Mihai; Thorup, Mikkel
4
2011
Maximum overhang. Zbl 1229.00005
Paterson, Mike; Peres, Yuval; Thorup, Mikkel; Winkler, Peter; Zwick, Uri
4
2009
Priority sampling for estimation of arbitrary subset sums. Zbl 1326.68036
Duffield, Nick G.; Lund, Carsten; Thorup, Mikkel
4
2007
Black box for constant-time insertion in priority queues (note). Zbl 1321.68232
Alstrup, Stephen; Husfeldt, Thore; Rauhe, Theis; Thorup, Mikkel
4
2005
Space efficient dynamic stabbing with fast queries. Zbl 1192.68143
Thorup, Mikkel
4
2003
Dynamic graph algorithms with applications. Zbl 0966.68605
Thorup, Mikkel; Karger, David R.
4
2000
Decremental dynamic connectivity. Zbl 0957.68091
Thorup, Mikkel
4
1999
Faster worst case deterministic dynamic connectivity. Zbl 1397.68142
Kejlberg-Rasmussen, Casper; Kopelowitz, Tsvi; Pettie, Seth; Thorup, Mikkel
3
2016
Algorithms and estimators for summarization of unaggregated data streams. Zbl 1311.68010
Cohen, Edith; Duffield, Nick; Kaplan, Haim; Lund, Carstent; Thorup, Mikkel
3
2014
More compact oracles for approximate distances in undirected planar graphs. Zbl 1423.68350
Kawarabayashi, Ken-Ichi; Sommer, Christian; Thorup, Mikkel
3
2013
On the \(k\)-independence required by linear probing and minwise independence. Zbl 1288.68050
Pǎtraşcu, Mihai; Thorup, Mikkel
3
2010
Randomization does not help searching predecessors. Zbl 1302.68102
Pǎtraşcu, Mihai; Thorup, Mikkel
3
2007
Union-find with constant time deletions. Zbl 1084.68026
Alstrup, Stephen; Gørtz, Inge Li; Rauhe, Theis; Thorup, Mikkel; Zwick, Uri
3
2005
Quick and good facility location. Zbl 1094.68123
Thorup, Mikkel
3
2003
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
Optimal pointer algorithms for finding nearest common ancestors in dynamic trees. Zbl 0951.68180
Alstrup, Stephen; Thorup, Mikkel
3
2000
Even strongly universal hashing is pretty fast. Zbl 0956.68509
Thorup, Mikkel
3
2000
Sampling to provide or to bound: With applications to fully dynamic graph algorithms. Zbl 0888.68065
Henzinger, Monika R.; Thorup, Mikkel
3
1997
Fast comparison of evolutionary trees. Zbl 1096.92501
Farach, Martin; Thorup, Mikkel
3
1995
Fast fencing. Zbl 1427.68323
Abrahamsen, Mikkel; Adamaszek, Anna; Bringmann, Karl; Cohen-Addad, Vincent; Mehr, Mehran; Rotenberg, Eva; Roytman, Alan; Thorup, Mikkel
2
2018
Construction and impromptu repair of an MST in a distributed network with \(o(m)\) communication. Zbl 1333.68213
King, Valerie; Kutten, Shay; Thorup, Mikkel
2
2015
Approximately minwise independence with twisted tabulation. Zbl 1417.68037
Dahlgaard, Søren; Thorup, Mikkel
2
2014
Mihai Pǎtraşcu: obituary and open problems. Zbl 1395.01075
Thorup, Mikkel
2
2013
Learn more, sample less: control of volume and variance in network measurement. Zbl 1296.94015
Duffield, Nick; Lund, Carsten; Thorup, Mikkel
2
2005
Generalized dominators for structured programs. Zbl 0961.68021
Alstrup, S.; Lauridsen, P. W.; Thorup, M.
2
2000
Deterministic edge connectivity in near-linear time. Zbl 1426.68217
Kawarabayashi, Ken-Ichi; Thorup, Mikkel
1
2019
On the \(k\)-independence required by linear probing and minwise independence. Zbl 1398.68118
Pǎtraşcu, Mihai; Thorup, Mikkel
1
2016
Finding the maximum subset with bounded convex curvature. Zbl 1387.68224
Abrahamsen, Mikkel; Thorup, Mikkel
1
2016
RAM-efficient external memory sorting. Zbl 1331.68067
Arge, Lars; Thorup, Mikkel
1
2015
From independence to expansion and back again. Zbl 1321.68219
Christiani, Tobias; Pagh, Rasmus; Thorup, Mikkel
1
2015
Union-find with constant time deletions. Zbl 1398.68101
Alstrup, Stephen; Thorup, Mikkel; Gørtz, Inge Li; Rauhe, Theis; Zwick, Uri
1
2014
RAM-efficient external memory sorting. Zbl 1329.68089
Arge, Lars; Thorup, Mikkel
1
2013
Don’t rush into a union, take time to find your roots. Zbl 1288.68134
Pătraşcu, Mihai; Thorup, Mikkel
1
2011
Efficient stream sampling for variance-optimal estimation of subset sums. Zbl 1231.62010
Cohen, Edith; Duffield, Nick; Kaplan, Haim; Lund, Carsten; Thorup, Mikkel
1
2011
Deterministic edge connectivity in near-linear time. Zbl 1426.68217
Kawarabayashi, Ken-Ichi; Thorup, Mikkel
1
2019
Fast fencing. Zbl 1427.68323
Abrahamsen, Mikkel; Adamaszek, Anna; Bringmann, Karl; Cohen-Addad, Vincent; Mehr, Mehran; Rotenberg, Eva; Roytman, Alan; Thorup, Mikkel
2
2018
Faster worst case deterministic dynamic connectivity. Zbl 1397.68142
Kejlberg-Rasmussen, Casper; Kopelowitz, Tsvi; Pettie, Seth; Thorup, Mikkel
3
2016
On the \(k\)-independence required by linear probing and minwise independence. Zbl 1398.68118
Pǎtraşcu, Mihai; Thorup, Mikkel
1
2016
Finding the maximum subset with bounded convex curvature. Zbl 1387.68224
Abrahamsen, Mikkel; Thorup, Mikkel
1
2016
Deterministic global minimum cut of a simple graph in near-linear time. Zbl 1321.05268
Kawarabayashi, Ken-ichi; Thorup, Mikkel
5
2015
Adjacency labeling schemes and induced-universal graphs. Zbl 1321.05226
Alstrup, Stephen; Kaplan, Haim; Thorup, Mikkel; Zwick, Uri
5
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
2
2015
RAM-efficient external memory sorting. Zbl 1331.68067
Arge, Lars; Thorup, Mikkel
1
2015
From independence to expansion and back again. Zbl 1321.68219
Christiani, Tobias; Pagh, Rasmus; Thorup, Mikkel
1
2015
Coloring 3-colorable graphs with \(o(n^{1/5})\) colors. Zbl 1359.05123
Kawarabayashi, Ken-ichi; Thorup, Mikkel
4
2014
Algorithms and estimators for summarization of unaggregated data streams. Zbl 1311.68010
Cohen, Edith; Duffield, Nick; Kaplan, Haim; Lund, Carstent; Thorup, Mikkel
3
2014
Approximately minwise independence with twisted tabulation. Zbl 1417.68037
Dahlgaard, Søren; 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
1
2014
Bottom-\(k\) and priority sampling, set similarity and subset sums with minimal independence. Zbl 1293.68107
Thorup, Mikkel
5
2013
More compact oracles for approximate distances in undirected planar graphs. Zbl 1423.68350
Kawarabayashi, Ken-Ichi; Sommer, Christian; Thorup, Mikkel
3
2013
Mihai Pǎtraşcu: obituary and open problems. Zbl 1395.01075
Thorup, Mikkel
2
2013
RAM-efficient external memory sorting. Zbl 1329.68089
Arge, Lars; Thorup, Mikkel
1
2013
The power of simple tabulation hashing. Zbl 1281.68089
Pǎtraşcu, Mihai; Thorup, Mikkel
6
2012
Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation. Zbl 1246.68107
Thorup, Mikkel; Zhang, Yin
6
2012
The minimum \(k\)-way cut of bounded size is fixed-parameter tractable. Zbl 1292.68094
Kawarabayashi, Ken-ichi; Thorup, Mikkel
15
2011
The power of simple tabulation hashing. Zbl 1288.68056
Patrascu, Mihai; Thorup, Mikkel
4
2011
Don’t rush into a union, take time to find your roots. Zbl 1288.68134
Pătraşcu, Mihai; Thorup, Mikkel
1
2011
Efficient stream sampling for variance-optimal estimation of subset sums. Zbl 1231.62010
Cohen, Edith; Duffield, Nick; Kaplan, Haim; Lund, Carsten; Thorup, Mikkel
1
2011
Regular expression matching with multi-strings and intervals. Zbl 1288.68299
Bille, Philip; Thorup, Mikkel
9
2010
Changing base without losing space. Zbl 1293.68118
Dodis, Yevgeniy; Patrascu, Mihai; Thorup, Mikkel
8
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
1
2010
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
Faster regular expression matching. Zbl 1248.68576
Bille, Philip; Thorup, Mikkel
5
2009
Maximum overhang. Zbl 1229.00005
Paterson, Mike; Peres, Yuval; Thorup, Mikkel; Winkler, Peter; Zwick, Uri
4
2009
Stream sampling for variance-optimal estimation of subset sums. Zbl 1426.62024
Cohen, Edith; Duffield, Nick; Kaplan, Haim; Lund, Carsten; Thorup, Mikkel
1
2009
Higher lower bounds for near-neighbor and further rich problems. Zbl 1200.68081
Pătraşcu, Mihai; 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
14
2008
Compact name-independent routing with minimum stretch. Zbl 1445.68143
Abraham, Ittai; Gavoille, Cyril; Malkhi, Dahlia; Nisan, Noam; Thorup, Mikkel
12
2008
Minimum \(k\)-way cuts via deterministic greedy tree packing. Zbl 1231.68185
Thorup, Mikkel
12
2008
Speeding up dynamic shortest-path algorithms. Zbl 1243.90221
Buriol, Luciana S.; Resende, Mauricio G. C.; Thorup, Mikkel
11
2008
Roundtrip spanners and roundtrip routing in directed graphs. Zbl 1420.68159
Roditty, Iam; Thorup, Mikkel; Zwick, Uri
1
2008
Dynamic ordered sets with exponential search trees. Zbl 1292.68038
Andersson, Arne; Thorup, Mikkel
22
2007
Equivalence between priority queues and sorting. Zbl 1326.68113
Thorup, Mikkel
8
2007
Survivable IP network design with OSPF routing. Zbl 1131.90319
Buriol, L. S.; Resende, M. G. C.; Thorup, M.
8
2007
Priority sampling for estimation of arbitrary subset sums. Zbl 1326.68036
Duffield, Nick G.; Lund, Carsten; Thorup, Mikkel
4
2007
Randomization does not help searching predecessors. Zbl 1302.68102
Pǎtraşcu, Mihai; Thorup, Mikkel
3
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
27
2006
Spanners and emulators with sublinear distance errors. Zbl 1192.05041
Thorup, Mikkel; Zwick, Uri
21
2006
Melding priority queues. Zbl 1321.68228
Mendelson, Ran; Tarjan, Robert E.; Thorup, Mikkel; Zwick, Uri
1
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
Approximate distance oracles. Zbl 1175.68303
Thorup, Mikkel; Zwick, Uri
168
2005
Deterministic constructions of approximate distance oracles and spanners. Zbl 1082.68087
Roditty, Liam; Thorup, Mikkel; Zwick, Uri
125
2005
Maintaining information in fully dynamic trees with top trees. Zbl 1321.68211
Alstrup, Stephen; Holm, Jacob; Lichtenberg, Kristian De; Thorup, Mikkel
22
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.
22
2005
Worst-case update times for fully-dynamic all-pairs shortest paths. Zbl 1192.68493
Thorup, Mikkel
14
2005
Quick \(k\)-median, \(k\)-center, and facility location for sparse graphs. Zbl 1099.68136
Thorup, Mikkel
5
2005
Black box for constant-time insertion in priority queues (note). Zbl 1321.68232
Alstrup, Stephen; Husfeldt, Thore; Rauhe, Theis; Thorup, Mikkel
4
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
44
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.
33
2004
OPT versus LOAD in dynamic storage allocation. Zbl 1101.68599
Buchsbaum, Adam L.; Karloff, Howard; Kenyon, Claire; Reingold, Nick; Thorup, Mikkel
15
2004
Increasing internet capacity using local search. Zbl 1069.90024
Fortz, Bernard; Thorup, Mikkel
15
2004
Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles. Zbl 1095.68628
Thorup, Mikkel
12
2004
Integer priority queues with decrease key in constant time and the single source shortest paths problem. Zbl 1084.68030
Thorup, Mikkel
11
2004
Tabulation based 4-universal hashing with applications to second moment estimation. Zbl 1318.68198
Thorup, Mikkel; Zhang, Yin
8
2004
Melding priority queues. Zbl 1095.68577
Mendelson, Ran; Tarjan, Robert E.; Thorup, Mikkel; Zwick, Uri
1
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
11
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
6
2002
Oracles for distances avoiding a link-failure. Zbl 1093.68614
Demetrescu, Camil; Thorup, Mikkel
1
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
52
2001
Approximate distance oracles. Zbl 1323.05126
Thorup, Mikkel; Zwick, Uri
17
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
1
2001
Dynamic string searching. Zbl 0987.68022
Andersson, Arne; Thorup, Mikkel
1
2001
Near-optimal fully-dynamic graph connectivity. Zbl 1296.05110
Thorup, Mikkel
22
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
17
2000
On RAM priority queues. Zbl 0968.68037
Thorup, Mikkel
13
2000
Tight(er) worst-case bounds on dynamic searching and priority queues. Zbl 1296.68038
Andersson, Arne A.; Thorup, Mikkel
12
2000
Maintaining center and median in dynamic trees. Zbl 0966.68510
Alstrup, Stephen; Holm, Jacob; Thorup, Mikkel
8
2000
Floats, integers, and single source shortest paths. Zbl 0951.68025
Thorup, Mikkel
8
2000
Dynamic graph algorithms with applications. Zbl 0966.68605
Thorup, Mikkel; Karger, David R.
4
2000
Optimal pointer algorithms for finding nearest common ancestors in dynamic trees. Zbl 0951.68180
Alstrup, Stephen; Thorup, Mikkel
3
2000
Even strongly universal hashing is pretty fast. Zbl 0956.68509
Thorup, Mikkel
3
2000
Generalized dominators for structured programs. Zbl 0961.68021
Alstrup, S.; Lauridsen, P. W.; Thorup, M.
2
2000
Undirected single-source shortest paths with positive integer weights in linear time. Zbl 1065.68597
Thorup, Mikkel
41
1999
On the approximability of numerical taxonomy (fitting distances by tree metrics). Zbl 1012.65015
Agarwala, Richa; Bafna, Vineet; Farach, Martin; Paterson, Mike; Thorup, Mikkel
17
1999
Dominators in linear time. Zbl 0939.68158
Alstrup, Stephen; Harel, Dov; Lauridsen, Peter W.; Thorup, Mikkel
15
1999
Fusion trees can be implemented with \(AC^0\) instructions only. Zbl 0915.68121
Andersson, Arne; Miltersen, Peter Bro; Thorup, Mikkel
11
1999
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.
10
1999
Decremental dynamic connectivity. Zbl 0957.68091
Thorup, Mikkel
4
1999
All structured programs have small tree width and good register allocation. Zbl 0924.68023
Thorup, Mikkel
20
1998
String matching in Lempel-Ziv compressed strings. Zbl 0899.68046
Farach, M.; Thorup, M.
15
1998
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
9
1998
...and 19 more Documents
all top 5

Cited by 1,354 Authors

14 Italiano, Giuseppe Francesco
14 Navarro, Gonzalo
14 Roditty, Liam
13 Thorup, Mikkel
12 Bille, Philip
11 Baswana, Surender
11 Gavoille, Cyril
11 Resende, Mauricio G. C.
10 Dragan, Feodor F.
10 Georgiadis, Loukas
9 Gørtz, Inge Li
9 Mulzer, Wolfgang Johann Heinrich
9 Neiman, Ofer
9 Rauch Henzinger, Monika
8 Chan, Timothy Moon-Yew
8 Elkin, Michael
8 Kaplan, Haim
8 Nekrich, Yakov
8 Peleg, David
8 Pettie, Seth
8 Proietti, Guido
7 Chepoi, Victor D.
7 Fortz, Bernard
7 Gawrychowski, Paweł
7 Kavitha, Telikepalli
7 Mozes, Shay
7 Porat, Ely
7 Seiferth, Paul
7 Weimann, Oren
6 Demaine, Erik D.
6 Hagerup, Torben
6 Korman, Amos
6 Leucci, Stefano
6 Munro, J. Ian
6 Pelc, Andrzej
6 Saurabh, Saket
6 Tsichlas, Kostas
6 Xu, Chao
5 Abraham, Ittai
5 Amir, Amihood
5 Bilò, Davide
5 Chekuri, Chandra S.
5 Elmasry, Amr
5 Filtser, Arnold
5 Fomin, Fedor V.
5 Gualà, Luciano
5 Hajiaghayi, Mohammad Taghi
5 Jansson, Jesper
5 Kawarabayashi, Ken-ichi
5 Klein, Philip N.
5 Levy, Avivit
5 Lokshtanov, Daniel
5 Naor, Assaf
5 Nelson, Jelani
5 Parotsidis, Nikos
5 Pilipczuk, Marcin
5 Raman, Venkatesh
5 Rytter, Wojciech
5 Sen, Sandeep
5 Shalom, B. Riva
5 Sohler, Christian
5 Sung, Wing-Kin
5 Zwick, Uri
4 Abboud, Amir
4 Abrahamsen, Mikkel
4 Alstrup, Stephen
4 Ausiello, Giorgio
4 Berry, Vincent
4 Bose, Prosenjit K.
4 Chandrasekaran, Karthekeyan
4 Chechik, Shiri
4 Czumaj, Artur
4 Demetrescu, Camil
4 Fredriksson, Kimmo
4 Golovach, Petr A.
4 Grabowski, Szymon
4 Han, Yijie
4 Landau, Gad M.
4 Liberti, Leo
4 Makris, Christos H.
4 Raman, Rajeev
4 Sadakane, Kunihiko
4 Stølting Brodal, Gerth
4 Takaoka, Tadao
4 Tsakalidis, Athanasios K.
4 ümit, Hakan
4 Vaxès, Yann
4 Warnow, Tandy J.
4 Xiao, Mingyu
3 Altın, Ayşegül
3 Azadeh, Ali
3 Bérczi, Kristóf
3 Berman, Piotr
3 Boria, Nicolas
3 Buriol, Luciana S.
3 Censor-Hillel, Keren
3 Chen, Jian-er
3 Choudhary, Keerti
3 Cohen, Michael B.
3 Colella, Feliciano
...and 1,254 more Authors
all top 5

Cited in 103 Serials

94 Theoretical Computer Science
89 Algorithmica
45 Discrete Applied Mathematics
32 Information Processing Letters
31 SIAM Journal on Computing
25 Journal of Computer and System Sciences
23 Journal of Discrete Algorithms
19 Theory of Computing Systems
18 Information and Computation
16 SIAM Journal on Discrete Mathematics
14 Computational Geometry
13 Computers & Operations Research
13 Distributed Computing
10 Mathematical Programming. Series A. Series B
9 Discrete & Computational Geometry
8 Annals of Operations Research
8 European Journal of Operational Research
6 International Journal of Foundations of Computer Science
5 Discrete Mathematics
5 Networks
5 Journal of Combinatorial Optimization
4 International Transactions in Operational Research
4 Journal of Graph Algorithms and Applications
4 Computer Science Review
3 American Mathematical Monthly
3 Applied Mathematics and Computation
3 Computing
3 Operations Research Letters
3 Discrete Optimization
3 Optimization Letters
3 Algorithms
2 Israel Journal of Mathematics
2 Nuclear Physics. B
2 Information Sciences
2 Operations Research
2 European Journal of Combinatorics
2 Combinatorica
2 Journal of Automated Reasoning
2 Journal of Cryptology
2 Random Structures & Algorithms
2 Pattern Recognition
2 Cybernetics and Systems Analysis
2 Computational Optimization and Applications
2 Top
2 Constraints
2 Journal of the ACM
2 Journal of Machine Learning Research (JMLR)
2 ACM Journal of Experimental Algorithmics
1 ACM Computing Surveys
1 Acta Informatica
1 Artificial Intelligence
1 Computers & Mathematics with Applications
1 Journal of Computational Physics
1 Journal of Mathematical Biology
1 Journal of Statistical Physics
1 ACM Transactions on Database Systems
1 Advances in Mathematics
1 The Annals of Statistics
1 Biometrical Journal
1 Inventiones Mathematicae
1 Journal of Mathematical Psychology
1 Mathematics of Operations Research
1 Results in Mathematics
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 MSCS. Mathematical Structures in Computer Science
1 Journal of Global Optimization
1 Geometric and Functional Analysis. GAFA
1 Linear Algebra and its Applications
1 Journal of Knot Theory and its Ramifications
1 Advances in Applied Clifford Algebras
1 The Electronic Journal of Combinatorics
1 Journal of Functional Programming
1 Journal of Heuristics
1 INFORMS Journal on Computing
1 Mathematical Problems in Engineering
1 Journal of Scheduling
1 Data Mining and Knowledge Discovery
1 Journal of the European Mathematical Society (JEMS)
1 Engineering Computations
1 RAIRO. Operations Research
1 Journal of Systems Science and Complexity
1 Natural Computing
1 Journal of Applied Mathematics and Computing
1 ACM Transactions on Computational Logic
1 4OR
1 Science in China. Series F
1 The Annals of Applied Statistics
1 Journal of Commutative Algebra
1 Japanese Journal of Mathematics. 3rd Series
1 Acta Universitatis Sapientiae. Informatica
1 Mathematical Programming Computation
1 RAIRO. Theoretical Informatics and Applications
1 ACM Transactions on Algorithms
1 Diskretnyĭ Analiz i Issledovanie Operatsiĭ
...and 3 more Serials

Citations by Year

Wikidata Timeline

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