Edit Profile (opens in new tab) Thorup, Mikkel Co-Author Distance Author ID: thorup.mikkel Published as: Thorup, Mikkel; Thorup, M. External Links: MGP · Wikidata · dblp · GND Documents Indexed: 160 Publications since 1991, including 1 Additional arXiv Preprint 1 Contribution as Editor Co-Authors: 106 Co-Authors with 123 Joint Publications 3,631 Co-Co-Authors 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 all top 5 Serials 13 SIAM Journal on Computing 10 Journal of the ACM 9 ACM Transactions on Algorithms 6 Journal of Algorithms 3 Algorithmica 2 American Mathematical Monthly 2 Journal of Computer and System Sciences 2 Networks 2 Theoretical Computer Science 2 Information and Computation 1 Acta Informatica 1 Discrete Applied Mathematics 1 IEEE Transactions on Information Theory 1 Information Processing Letters 1 Mathematics of Operations Research 1 Discrete & Computational Geometry 1 SIAM Journal on Discrete Mathematics 1 Annals of Operations Research 1 Random Structures & Algorithms 1 Computational Optimization and Applications 1 Combinatorics, Probability and Computing 1 Electronic Communications in Probability 1 INFORMS Journal on Computing 1 Bulletin of the European Association for Theoretical Computer Science EATCS 1 4OR 1 ACM Journal of Experimental Algorithmics all top 5 Fields 150 Computer science (68-XX) 53 Combinatorics (05-XX) 25 Operations research, mathematical programming (90-XX) 5 Biology and other natural sciences (92-XX) 4 Statistics (62-XX) 3 Numerical analysis (65-XX) 3 Information and communication theory, circuits (94-XX) 2 General and overarching topics; collections (00-XX) 2 Probability theory and stochastic processes (60-XX) 1 History and biography (01-XX) 1 Sequences, series, summability (40-XX) 1 Geometry (51-XX) 1 Convex and discrete geometry (52-XX) 1 Differential geometry (53-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 1 Mathematics education (97-XX) Publications by Year all cited Publications top 5 cited Publications 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 cited Publications top 5 cited Publications 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 all top 5 Cited in 35 Fields 904 Computer science (68-XX) 445 Combinatorics (05-XX) 197 Operations research, mathematical programming (90-XX) 40 Biology and other natural sciences (92-XX) 31 Information and communication theory, circuits (94-XX) 26 Numerical analysis (65-XX) 23 Statistics (62-XX) 21 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 17 Probability theory and stochastic processes (60-XX) 8 Statistical mechanics, structure of matter (82-XX) 7 Functional analysis (46-XX) 6 Mathematical logic and foundations (03-XX) 6 Convex and discrete geometry (52-XX) 5 General topology (54-XX) 5 Quantum theory (81-XX) 4 Order, lattices, ordered algebraic structures (06-XX) 4 Linear and multilinear algebra; matrix theory (15-XX) 4 Functions of a complex variable (30-XX) 3 Group theory and generalizations (20-XX) 3 Geometry (51-XX) 2 General and overarching topics; collections (00-XX) 2 Number theory (11-XX) 2 Partial differential equations (35-XX) 2 Differential geometry (53-XX) 2 Manifolds and cell complexes (57-XX) 1 Commutative algebra (13-XX) 1 Algebraic geometry (14-XX) 1 Category theory; homological algebra (18-XX) 1 Dynamical systems and ergodic theory (37-XX) 1 Sequences, series, summability (40-XX) 1 Approximations and expansions (41-XX) 1 Algebraic topology (55-XX) 1 Mechanics of particles and systems (70-XX) 1 Systems theory; control (93-XX) 1 Mathematics education (97-XX) 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.