Mikkel Thorup
Professor
- 2004
Integer priority queues with decrease key in constant time and the single source shortest paths problem
Thorup, Mikkel, 2004, In: Journal of Computer and System Sciences. 69, 3, p. 330-353 24 p.Research output: Contribution to journal › Journal article › Research › peer-review
Melding Priority Queues
Mendelson, R., Tarjan, R., Thorup, Mikkel & Zwick, U., 2004, Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT). Springer, p. 223-235 13 p. (Lecture notes in computer science, Vol. 3111).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
OPT versus LOAD in dynamic storage allocation
Buchsbaum, A. L., Karloff, H. J., Kenyon, C., Reingold, N. & Thorup, Mikkel, 2004, In: SIAM Journal on Computing. 33, 3, p. 632-646 15 p.Research output: Contribution to journal › Journal article › Research › peer-review
On Adaptive Integer Sorting
Pagh, A., Pagh, R. & Thorup, Mikkel, 2004, Proceedings of the 12th European Symposium on Algorithms (ESA), LNCS 3221. Springer, p. 556-579 24 p. (Lecture notes in computer science, Vol. 3221).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut
Karger, D., Klein, P., Stein, C., Thorup, Mikkel & Young, N., 2004, In: Mathematics of Operations Research. 29, 3, p. 436-461 26 p.Research output: Contribution to journal › Journal article › Research › peer-review
Tabulation Based 4-Universal Hashing with Applications to Second Moment Estimation
Thorup, Mikkel & Zhang, Y., 2004. 10 p.Research output: Contribution to conference › Paper › Research › peer-review
- 2005
A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing
Buriol, L. S., Resende, M. G. C., Ribeiro, C. C. & Thorup, Mikkel, 2005, In: Networks. 46, 1, p. 36-56 21 p.Research output: Contribution to journal › Journal article › Research › peer-review
Approximate Distance Oracles
Thorup, Mikkel & Zwick, U., 2005, In: jacm. 52, 1, p. 1-24 24 p.Research output: Contribution to journal › Journal article › 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
Deterministic Constructions of Approximate Distance Oracles and Spanners
Roditty, L., Thorup, Mikkel & Zwick, U., 2005, Proceedings of the 32th International Colloquium on Automata Languages, and Programming (ICALP), LNCS 3580. p. 261-272 12 p. (Lecture notes in computer science, Vol. 3580).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
Estimating Flow Distributions from Sampled Flow Statistics
Duffield, N., Lund, C. & Thorup, Mikkel, 2005, In: ACM/IEEE Transactions on Networking. 13, 5, p. 933-946 14 p.Research output: Contribution to journal › Journal article › Research › peer-review
Learn More, Sample Less: Control of Volume and Variance in Network Measurement
Duffield, N., Lund, C. & Thorup, Mikkel, 2005, In: IEEE Transactions on Information Theory. 51, 5, p. 1756-1775 20 p.Research output: Contribution to journal › Journal article › Research › peer-review
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
Optimal Combination of Sampled Network Measurements
Duffield, N., Lund, C. & Thorup, Mikkel, 2005, Proceedings the ACM Internet Measurement Conference (IMC). p. 91-104 14 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Quick k-Median, k-Center, and Facility Location for Sparse Graphs
Thorup, Mikkel, 2005, In: sicomp. 34, 2, p. 405-432 28 p.Research output: Contribution to journal › Journal article › 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
Worst-Case Update Times for Fully-Dynamic All-Pairs Shortest Paths
Thorup, Mikkel, 2005, Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC). Association for Computing Machinery, p. 112-119 8 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- 2006
Confidence Intervals for Priority Sampling
Thorup, Mikkel, 2006, Proceedings the ACM IFIP Conference on Measurement and Modeling of Computer Systems (SIGMETRICS/Performance). p. 252-263 12 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Does Path Cleaning Help in Dynamic All-Pairs Shortest Paths
Demetrescu, C., Faruolo, P., Italiano, G. F. & Thorup, Mikkel, 2006, Proceedings of the 14th European Symposium on Algorithms (ESA), LNCS 4168. p. 556-579 24 p. (Lecture notes in computer science, Vol. 4168).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Higher Lower Bounds for Near-Neighbor and Further Rich Problems
Patracu, M. & Thorup, Mikkel, 2006, Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS). p. 646-654 9 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Melding Priority Queues
Mendelson, R., Tarjan, R., Thorup, Mikkel & Zwick, U., 2006, In: ACM Transactions on Algorithms. 2, 4, p. 535-557 23 p.Research output: Contribution to journal › Conference article › Research › peer-review
Spanners and emulators with sublinear distance errors
Thorup, Mikkel & Zwick, U., 2006, Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA). p. 802-809 8 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Time-Space Trade-Offs for Predecessor Search
Patracu, M. & Thorup, Mikkel, 2006, Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC). p. 232-240 9 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
- 2007
Algorithms and Estimators for Accurate Summarization of Internet Traffic
Cohen, E., Duffield, N., Kaplan, H., Lund, C. & Thorup, Mikkel, 2007, Proceedings the ACM Internet Measurement Conference (IMC). Association for Computing Machinery, p. 265-278 14 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Compact Oracles for Approximate Distances around Obstacles in the Plane
Thorup, Mikkel, 2007, Proceedings of the 15th European Symposium on Algorithms (ESA), LNCS 4698. p. 383-394 12 p. (Lecture notes in computer science, Vol. 4698).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
Equivalence between Priority Queues and Sorting
Thorup, Mikkel, 2007, In: Journal of the ACM. 54, 6, p. Article 28Research output: Contribution to journal › Journal article › Research › peer-review
Fully-Dynamic Min-Cut
Thorup, Mikkel, 2007, In: Combinatorica. 27, 1, p. 91-127 37 p.Research output: Contribution to journal › Journal article › Research › peer-review
On the variance of subset sum estimation
Szegedy, M. & Thorup, Mikkel, 2007, Proceedings of the 15th European Symposium on Algorithms (ESA), LNCS 4698. p. 75-86 12 p. (Lecture notes in computer science, Vol. 4698).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Planning for Fast Connectivity Updates
Patracu, M. & Thorup, Mikkel, 2007, Proceedings of the 48th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, p. 263-271 9 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Priority sampling for estimation of arbitrary subset sums
Duffield, N., Lund, C. & Thorup, Mikkel, 2007, In: Journal of the ACM. 54, 6, p. Article 32Research output: Contribution to journal › Journal article › Research › peer-review
Randomization Does Not Help Searching Predecessors
Patracu, M. & Thorup, Mikkel, 2007, Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA). p. 555-564 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Sketching Unaggregated Data Streams for Subpopulation-Size Queries
Cohen, E., Duffield, N., Kaplan, H., Lund, C. & Thorup, Mikkel, 2007, Proceedings of the 26th Annual ACM Symposium on Principles of Database Systems (PODS). Association for Computing Machinery, p. 253-262 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Survivable IP network design with OSPF routing
Buriol, L. S., Resende, M. G. C. & Thorup, Mikkel, 2007, In: Networks. 49, 1, p. 51-64 14 p.Research output: Contribution to journal › Journal article › Research › peer-review
- 2008
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
Confident estimation for multistage measurement sampling and aggregation
Cohen, E., Duffield, N., Lund, C. & Thorup, Mikkel, 2008, Proceedings the ACM IFIP Conference on Measurement and Modeling of Computer Systems (SIGMETRICS/Performance). ACM, p. 109-120 12 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Maximum overhang
Paterson, M., Peres, Y., Thorup, Mikkel, Winkler, P. & Zwick, U., 2008, Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, p. 756-765 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Minimum k-way cuts via deterministic greedy tree packing
Thorup, Mikkel, 2008, Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC). ACM, p. 159-166 8 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Oracles for Distances Avoiding a Failed Node or Link
Demetrescu, C., Thorup, Mikkel, Chowdhury, R. A. & Ramachandran, V., 2008, In: sicomp. 37, 5, p. 1299-1318 20 p.Research output: Contribution to journal › Journal article › Research › peer-review
Roundtrip Spanners and Roundtrip Routing in Directed Graphs
Roditty, L., Thorup, Mikkel & Zwick, U., 2008, In: ACM Transactions on Algorithms. 4, 3, p. Article 29Research output: Contribution to journal › Journal article › Research › peer-review
Speeding up Dynamic Shortest-Path Algorithms
Buriol, L. S., Resende, M. G. C. & Thorup, Mikkel, 2008, In: I N F O R M S Journal on Computing. 20, 2, p. 191-204 14 p.Research output: Contribution to journal › Journal article › Research › peer-review
- 2009
Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets
Cohen, E., Duffield, N. G., Kaplan, H., Lund, C. & Thorup, Mikkel, 2009, In: Proceedings of Very Large Databases (VLDB) Endowment. 2, 1, p. 431-442 12 p.Research output: Contribution to journal › Journal article › Research › peer-review
Discounted deterministic Markov decision processes and discounted all-pairs shortest paths
Madani, O., Thorup, Mikkel & Zwick, U., 2009, Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, p. 958-967 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Faster Regular Expression Matching
Bille, P. & Thorup, Mikkel, 2009, Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 5555. Springer, p. 171-182 12 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Higher Lower Bounds for Near-Neighbor and Further Rich Problems
Patracu, M. & Thorup, Mikkel, 2009, In: sicomp. 39, 2, p. 730-741 12 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
Maximum overhang
Paterson, M., Peres, Y., Thorup, Mikkel, Winkler, P. & Zwick, U., 2009, In: American Mathematical Monthly. 116, 9, p. 763-787 25 p.Research output: Contribution to journal › Journal article › Research › peer-review
Stream sampling for variance-optimal estimation of subset sums
Cohen, E., Duffield, N., Kaplan, H., Lund, C. & Thorup, Mikkel, 2009, Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, p. 1255-1264 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
String hashing for linear probing
Thorup, Mikkel, 2009, Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, p. 655-664 10 p.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
ID: 34257574
Most downloads
-
2506
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 -
133
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 -
105
downloads
Bottleneck paths and trees and deterministic graphical games
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Published