Mikkel Thorup
Professor
- Published
On sums of monotone random integer variables
Aamand, Anders, Alon, N., Houen, J. B. T. & Thorup, Mikkel, 2022, In: Electronic Communications in Probability. 27, p. 1-8 64.Research output: Contribution to journal › Journal article › Research › peer-review
- Published
Fast hashing with strong concentration bounds
Aamand, Anders, Knudsen, J. B. T., Knudsen, M. B. T., Rasmussen, Peter Michael Reichstein & Thorup, Mikkel, 2020, STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G. & Chuzhoy, J. (eds.). Association for Computing Machinery, p. 1265-1278 (Proceedings of the Annual ACM Symposium on Theory of Computing).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Disks in Curves of Bounded Convex Curvature
Aamand, Anders, Abrahamsen, Mikkel & Thorup, Mikkel, 2020, In: American Mathematical Monthly. 127, 7, p. 579-593 15 p.Research output: Contribution to journal › Journal article › Research › peer-review
- Published
Optimal Decremental Connectivity in Non-Sparse Graphs
Aamand, A., Karczmarz, A., Łącki, J., Parotsidis, N., Rasmussen, Peter Michael Reichstein & Thorup, Mikkel, 2023, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023. Etessami, K., Feige, U. & Puppis, G. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 1-17 6. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 261).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Power of d choices with simple tabulation
Aamand, Anders, Knudsen, M. B. T. & Thorup, Mikkel, 1 Jul 2018, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018. Kaklamanis, C., Marx, D., Chatzigiannakis, I. & Sannella, D. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 14 p. 5. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 107).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
No Repetition: Fast and Reliable Sampling with Highly Concentrated Hashing
Aamand, A., Das, D., Kipouridis, Evangelos, Knudsen, J. B. T., Rasmussen, Peter Michael Reichstein & Thorup, Mikkel, 2022, In: Proceedings of the VLDB Endowment. 15, 13, p. 3989-4001Research output: Contribution to journal › Conference article › Research › peer-review
- Published
Load balancing with dynamic set of balls and bins
Aamand, Anders, Knudsen, J. B. T. & Thorup, Mikkel, 2021, STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Khuller, S. & Williams, V. V. (eds.). Association for Computing Machinery, Inc, p. 1262-1275 (Proceedings of the Annual ACM Symposium on Theory of Computing).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Non-empty Bins with Simple Tabulation Hashing
Aamand, Anders & Thorup, Mikkel, 2 Jan 2019, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. Chan, T. M. (ed.). Society for Industrial and Applied Mathematics, p. 2498-2512Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research
- Published
Compact name-independent routing with minimum stretch
Abraham, I., Gavoille, C., Malkhi, D., Nisan, N. & Thorup, Mikkel, 2008, In: ACM Transactions on Algorithms. 4, 3, p. Article 37Research output: Contribution to journal › Journal article › Research › peer-review
- Published
Finding the maximum subset with bounded convex curvature
Abrahamsen, Mikkel & Thorup, Mikkel, 2016, 32nd International Symposium on Computational Geometry (SoCG 2016). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 17 p. 4. (Leibniz International Proceedings in Informatics, Vol. 51).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
How to Cut Corners and Get Bounded Convex Curvature
Abrahamsen, Mikkel & Thorup, Mikkel, 2023, In: Discrete and Computational Geometry. 69, p. 1195–1231,Research output: Contribution to journal › Journal article › Research › peer-review
- Published
Fast fencing
Abrahamsen, Mikkel, Adamaszek, A., Bringmann, K., Cohen-Addad, V., Mehr, M., Rotenberg, E., Roytman, A. & Thorup, Mikkel, 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, p. 564-573Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)
Agarwala, R., Bafna, V., Farach, M., Narayanan, B., Paterson, M. & Thorup, Mikkel, 1999, In: SIAM Journal on Computing. 28, 3, p. 1073 - 1085Research output: Contribution to journal › Journal article › Research › peer-review
On the Approximability of Numerical Taxonomy
Agarwala, R., Bafna, V., Farach, M., Narayanan, B., Paterson, M. & Thorup, Mikkel, 1996, Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms (SODA). p. 365-372 8 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Estimating Arbitrary Subset Sums with Few Probes
Alon, N., Duffield, N., Lund, C. & Thorup, Mikkel, 2005, Proceedings of the 24th Annual ACM Symposium on Principles of Database Systems (PODS). Association for Computing Machinery, p. 317-325 9 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Black box for constant-time insertion in priority queues (note)
Alstrup, Stephen, Husfeldt, T., Rauhe, T. & Thorup, Mikkel, 2005, In: ACM Transactions on Algorithms (TALG). 1, 1, p. 102-106 5 p.Research output: Contribution to journal › Journal article › Research › peer-review
Dominators in linear time
Alstrup, Stephen, Harel, D., Lauridsen, P. W. & Thorup, Mikkel, 1999, In: SIAM Journal on Computing. 28, 6, p. 2117-2132 16 p.Research output: Contribution to journal › Journal article › Research › peer-review
- Published
Generalized dominators for structured programs
Alstrup, Stephen, Lauridsen, P. W. & Thorup, Mikkel, 1996, Static Analysis. Springer Science+Business Media, p. 42-51 10 p. (Lecture notes in computer science, Vol. 1145).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Maintaining center and median in dynamic trees
Alstrup, Stephen, Holm, Jacob & Thorup, Mikkel, 2000, Algorithm Theory-SWAT 2000. Springer Science+Business Media, Vol. 1851. p. 46-56 11 p. (Lecture notes in computer science).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Optimal pointer algorithms for finding nearest common ancestors in dynamic trees
Alstrup, Stephen & Thorup, Mikkel, 2000, In: Journal of Algorithms. 35, 2, p. 169-188 20 p.Research output: Contribution to journal › Journal article › Research › peer-review
Generalized Dominators for Structured Programs
Alstrup, Stephen, Lauridsen, P. W. & Thorup, Mikkel, 2000, In: Algorithmica. 27, 3, p. 244-253 10 p.Research output: Contribution to journal › Journal article › Research › peer-review
- Published
Optimal pointer algorithms for finding nearest common ancestors in dynamic trees
Alstrup, Stephen & Thorup, Mikkel, 1996, Algorithm Theory—SWAT'96. Springer Science+Business Media, p. 212-222 11 p. (Lecture notes in computer science, Vol. 1097).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Union-find with constant time deletions
Alstrup, Stephen, Gørtz, I. L., Rauhe, T., Thorup, Mikkel & Zwick, U., 2005, Automata, Languages and Programming (ICALP). Springer, p. 78-89 12 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Finding cores of limited length
Alstrup, Stephen, Lauridsen, P. W., Sommerlund, P. & Thorup, Mikkel, 1997, Proceedings of the 5th International Workshop on Algorithms and Data Structures (WADS). Springer, Vol. 1272. p. 45-54 11 p. (Lecture notes in computer science).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Worst-case union-find with fast deletions
Alstrup, Stephen, Gørtz, I. L., Rauhe, T. & Thorup, Mikkel, 2003.Research output: Working paper › Research
Word encoding tree connectivity works
Alstrup, Stephen, Secher, J. P. & Thorup, Mikkel, 1999, In: DIKU Report.Research output: Contribution to journal › Journal article › Research
Maintaining information in fully dynamic trees with top trees
Alstrup, Stephen, Holm, J., Lichtenberg, K. D. & Thorup, Mikkel, 2005, In: ACM Transactions on Algorithms (TALG). 1, 2, p. 243-264 22 p.Research output: Contribution to journal › Journal article › Research › peer-review
- Published
Union-find with constant time deletions
Alstrup, Stephen, Thorup, Mikkel, Gørtz, I. L., Rauhe, T. & Zwick, U., 2014, In: A C M Transactions on Algorithms. 11, 1, 28 p., 6.Research output: Contribution to journal › Journal article › Research › peer-review
Diameter and distance in dynamic trees
Alstrup, Stephen, Holm, J., Jørgensen, K. & Thorup, Mikkel, 1996.Research output: Working paper › Research
- Published
Adjacency labeling schemes and induced-universal graphs
Alstrup, Stephen, Kaplan, H., Thorup, Mikkel & Zwick, U., 2015, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015: STOC '15. Association for Computing Machinery, p. 625-634 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Adjacency Labeling Schemes and Induced-Universal Graphs
Alstrup, Stephen, Kaplan, H., Thorup, Mikkel & Zwick, U., 2019, In: SIAM Journal on Discrete Mathematics. 33, 1, p. 116-137Research output: Contribution to journal › Journal article › Research › peer-review
- Published
Direct Routing on Trees
Alstrup, Stephen, Holm, J., de Lichtenberg, K. & Thorup, Mikkel, 1998, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms. p. 342-349 8 p. (9th ACM-SIAM Symposium on Discrete Algorithms (SODA)).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Minimizing diameters of dynamic trees
Alstrup, Stephen, Holm, J., de Lichtenberg, K. & Thorup, Mikkel, 1997, Automata, Languages and Programming. Springer Science+Business Media, p. 270-280 11 p. (Lecture notes in computer science, Vol. 1256).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Finding dominators in linear time
Alstrup, Stephen, Lauritzen, P. W. & Thorup, Mikkel, 1996, (DIKU Report).Research output: Working paper › Research
Efficient tree layout in a multilevel memory hierarchy
Alstrup, Stephen, Bender, M. A., Demaine, E. D., Farach-Colton, M., Rauhe, T. & Thorup, Mikkel, 2002, In: arXiv preprint cs/0211010.Research output: Contribution to journal › Journal article › Research
- Published
Word encoding tree connectivity works
Alstrup, Stephen, Secher, J. P. & Thorup, Mikkel, 2000, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms. p. 498-499 2 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Intra-domain traffic engineering with shortest path routing protocols
Altin, A., Fortz, B., Thorup, Mikkel & Ümit, H., 2013, In: Annals of Operations Research. 204, 1, p. 56-95 40 p.Research output: Contribution to journal › Journal article › Research › peer-review
Intra-domain traffic engineering with shortest path routing protocols
Altin, A., Fortz, B., Thorup, Mikkel & Ümit, H., 2009, In: 4OR. 7, 4, p. 301-335 35 p.Research output: Contribution to journal › Journal article › Research › peer-review
Fusion trees can be implemented with AC^0 instructions only
Andersson, A., Miltersen, P. B. & Thorup, Mikkel, 1999, In: Theoretical Computer Science. 215, 1-2, p. 337-344 8 p.Research output: Contribution to journal › Journal article › Research › peer-review
Tight(er) Worst-case Bounds on Dynamic Searching and Priority Queues
Andersson, A. & Thorup, Mikkel, 2000, Proceedings of the 32nd ACM Symposium on the Theory of Computing (STOC). p. 335-342 8 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Dynamic Ordered Sets with Exponential Search Trees
Andersson, A. & Thorup, Mikkel, 2007, In: Journal of the ACM. 54, 3, p. Article 13Research output: Contribution to journal › Journal article › Research › peer-review
A Pragmatic Implementation of Monotone Priority Queues
Andersson, A. & Thorup, Mikkel, 1996, In: Unpublished.Research output: Contribution to journal › Journal article › Research
Static Dictionaries on AC^0 RAMs: Query time log n/log log n) is necessary and sufficient
Andersson, A., Miltersen, P. B., Riis, S. & Thorup, Mikkel, 1996, Proceedings of the 37th IEEE Symposium on Foundations of Computer Science (FOCS). p. 441-450 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Dynamic string searching
Andersson, A. & Thorup, Mikkel, 2001, Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA). p. 307-308 2 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Load optimal MPLS routing with N+M labels
Applegate, D. & Thorup, Mikkel, 2003, Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). p. 555-565 11 p. (I E E E Infocom. Proceedings).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
Wireless coverage prediction via parametric shortest paths
Applegate, D., Archer, A., Johnson, D. S., Nikolova, E., Thorup, Mikkel & Yang, G., 2018, Proceedings of the Eighteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, Mobihoc '18 . ACM, p. 221-230Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
RAM-efficient external memory sorting
Arge, L. & Thorup, Mikkel, 2013, Algorithms and Computation: 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings. Cai, L., Cheng, S-W. & Lam, T-W. (eds.). Springer, p. 491-501 11 p. (Lecture notes in computer science, Vol. 8283).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- Published
RAM-efficient external memory sorting
Arge, L. & Thorup, Mikkel, 2015, In: Algorithmica. 73, 4, p. 623-636 14 p.Research output: Contribution to journal › Journal article › Research › peer-review
Untangling the balancing and searching of balanced binary search trees
Austern, M. H., Stroustrup, B., Thorup, Mikkel & Wilkinson, J., 2003, In: Software: Practice & Experience. 33, 13, p. 1273-1298 26 p.Research output: Contribution to journal › Journal article › Research › peer-review
ID: 34257574
Most downloads
-
2500
downloads
Coloring 3-colorable graphs with o(n 1/5) colors
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Published -
132
downloads
Incremental exact min-cut in poly-logarithmic amortized update time
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Published -
104
downloads
Bottleneck paths and trees and deterministic graphical games
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Published