Mikkel Thorup

Research output

Research output per year 1990 1996 1999 2000 2001 2002 2003 2004 2005 2007 2009 2013 2015 2016 2018 2019

• 126 Article in proceedings
• 73 Journal article
• 6 Working paper
• 1 Book
• 6 More
  • 1 Ph.D. thesis
  • 1 Conference abstract in proceedings
  • 1 Paper
  • 1 Comment/debate
  • 1 Conference article
  • 1 Other contribution

Research output per year

Research output per year

Search results

• 2019

  Adjacency Labeling Schemes and Induced-Universal Graphs

  Alstrup, S., Kaplan, H., Thorup, M. & Zwick, U., 2019, In: SIAM Journal on Discrete Mathematics. 33, 1, p. 116-137

  Research output: Contribution to journal › Journal article › Research › peer-review

  • Labeling Scheme 100%
  • Universal Graphs 99%
  • Adjacency 73%
  • Graph in graph theory 30%
  • Tournament 24%
  4 Citations (Scopus)

• Dynamic ordered sets with approximate queries, approximate heaps and soft heaps

  Thorup, M., Zamir, O. & Zwick, U., 2019, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. Chatzigiannakis, I., Baier, C., Leonardi, S. & Flocchini, P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 13 p. 95. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 132).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Heap 100%
  • Ordered Set 80%
  • Query 72%
  • Sorting 13%
  • Data Structures 12%

• Non-empty Bins with Simple Tabulation Hashing

  Aamand, A. & Thorup, M., 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-2512

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research

  • Hashing 100%
  • Bloom Filter 59%
  • False Positive 40%
  • Hash Function 19%
  • Paradigm 15%
• 2018

  Consistent Hashing with bounded loads

  Mirrokni, V., Thorup, M. & Zadimoghaddam, M., 2018, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Czumaj, A. (ed.). Society for Industrial and Applied Mathematics, p. 587-604 18 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Loads (forces) 100%
  • Bins 91%
  • Servers 53%
  • Resource allocation 23%
  • Dynamic loads 9%
  8 Citations (Scopus)

• Deterministic Edge Connectivity in Near-Linear Time

  Kawarabayashi, K. & Thorup, M., Dec 2018, In: Journal of the ACM. 66, 1, p. 1-50 4.

  Research output: Contribution to journal › Journal article › Research › peer-review

  • Concretes 100%
  • Set theory 94%
  15 Citations (Scopus)

• Dynamic bridge-finding in Õ(log² n) amortized time

  Holm, J., Rotenberg, E. & Thorup, M., 2018, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Czumaj, A. (ed.). Society for Industrial and Applied Mathematics, p. 35-52 18 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Update 100%
  • Dynamic Data Structures 80%
  • Perfect Matching 54%
  • Data Structures 52%
  • Linear Space 50%
  6 Citations (Scopus)

• Fast fencing

  Abrahamsen, M., Adamaszek, A., Bringmann, K., Cohen-Addad, V., Mehr, M., Rotenberg, E., Roytman, A. & Thorup, M., 2018, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, p. 564-573

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Curve 100%
  • Closed curve 54%
  • Costs 47%
  • Unit 33%
  • Unit Disk 28%
  1 Citation (Scopus)

• Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time

  Goranci, G., Henzinger, M. & Thorup, M., Mar 2018, In: ACM Transactions on Algorithms. 14, 2, 17.

  Research output: Contribution to journal › Journal article › Research › peer-review

  • Min-cut 100%
  • Minimum Cut 98%
  • Incremental Algorithm 79%
  • Update 70%
  • Insertion 40%
  5 Citations (Scopus)

• Power of d choices with simple tabulation

  Aamand, A., Knudsen, M. B. T. & Thorup, M., 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

  • Hash Function 100%
  • Ball 81%
  • Tie 47%
  • Hashing 26%
  • Time Constant 23%
  3 Citations (Scopus)

  10 Downloads (Pure)

• Proceedings, 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)

  Thorup, M. (ed.), 2018, IEEE. 996 p.

  Research output: Book/Report › Book › Research › peer-review

• Sample(x)=(a*x <=t) is a distinguisher with probability 1/8

  Thorup, M., 2018, In: SIAM Journal on Computing. 47, 6, p. 2510-2526

  Research output: Contribution to journal › Journal article › Research › peer-review

  • Sampling 100%
  • Hash functions 83%
  • Integer 69%
  • Overflow 58%
  • Hash Function 54%

• The entropy of backwards analysis

  Knudsen, M. B. T. & Thorup, M., 2018, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Czumaj, A. (ed.). Society for Industrial and Applied Mathematics, p. 867-880 14 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Entropy 100%
  • Random Permutation 58%
  • Permutation 50%
  • Randomness 31%
  • Triangulation 29%

• Wireless coverage prediction via parametric shortest paths

  Applegate, D., Archer, A., Johnson, D. S., Nikolova, E., Thorup, M. & Yang, G., 26 Jun 2018, Proceedings of the Eighteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, Mobihoc '18 . ACM, p. 221-230

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Approximation algorithms 100%
  • Wireless networks 72%
  • Antennas 59%
• 2017

  Coloring 3-colorable graphs with less than n^1/5 colors

  Kawarabayashi, K. & Thorup, M., Mar 2017, In: Journal of the ACM. 64, 1, 23 p., 4.

  Research output: Contribution to journal › Journal article › Research › peer-review

  • Coloring 100%
  • Color 60%
  • Polynomials 26%
  8 Citations (Scopus)

• Fast and powerful hashing using tabulation

  Thorup, M., 2017, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Chatzigiannakis, I., Indyk, P., Kuhn, F. & Muscholl, A. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2 p. 4. (Leibniz International Proceedings in Informatics, Vol. 80).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research

  12 Downloads (Pure)

• Fast and powerful hashing using tabulation

  Thorup, M., Jul 2017, In: Communications of the ACM. 60, 7, p. 94-101 8 p.

  Research output: Contribution to journal › Journal article › Research › peer-review

  • Hash functions 100%
  • Computer science 42%
  • Data structures 35%
  5 Citations (Scopus)

• Fast similarity sketching

  Dahlgaard, S., Knudsen, M. B. T. & Thorup, M., 10 Nov 2017, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, p. 663-671 9 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Sketching 100%
  • Similarity 58%
  • Similarity Search 56%
  • Random Function 25%
  • Sampling without Replacement 15%
  8 Citations (Scopus)

• Practical hash functions for similarity estimation and dimensionality reduction

  Dahlgaard, S., Knudsen, M. B. T. & Thorup, M., 2017, Neural Information Processing Systems 2017. Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S. & Garnett, R. (eds.). NIPS Proceedings, 11 p. (Advances in Neural Information Processing Systems, Vol. 30).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Hash functions 100%
  • Dimensionality reduction 92%
  • Nearest neighbor search 44%
  • Concretes 22%
  • Machine learning 12%
  10 Citations (Scopus)
• 2016

  Bottleneck paths and trees and deterministic graphical games

  Chechik, S., Kaplan, H., Thorup, M., Zamir, O. & Zwick, U., 1 Feb 2016, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Ollinger, N. & Vollmer, H. (eds.). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, p. 1-13 13 p. 27. (Leibniz International Proceedings in Informatics, Vol. 47).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Directed graphs 100%
  • Random access storage 93%
  1 Citation (Scopus)

  34 Downloads (Pure)

• Fast and powerful hashing using tabulation

  Thorup, M., 2016, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Lal, A., Akshay, S., Saurabh, S. & Sen, S. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2 p. 1. (Leibniz International Proceedings in Informatics, Vol. 65).

  Research output: Chapter in Book/Report/Conference proceeding › Conference abstract in proceedings › Research › peer-review

  33 Downloads (Pure)

• Faster worst case deterministic dynamic connectivity

  Kejlberg-Rasmussen, C., Kopelowitz, T., Pettie, S. & Thorup, M., 1 Aug 2016, 24th Annual European Symposium on Algorithms (ESA 2016). Sankowski, P. & Zaroliagis, C. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 53:1-53:15 15 p. 53. (Leibniz International Proceedings in Informatics, Vol. 57).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Data structures 100%
  9 Citations (Scopus)

  44 Downloads (Pure)

• Finding the maximum subset with bounded convex curvature

  Abrahamsen, M. & Thorup, M., 1 Jun 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

  • Curvature 100%
  • Subset 71%
  • Machining 61%
  • Connected Set 50%
  • Rough 41%
  1 Citation (Scopus)

  67 Downloads (Pure)

• Heavy hitters via cluster-preserving clustering

  Larsen, K. G., Nelson, J., Nguyen, H. L. & Thorup, M., 14 Dec 2016, Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science. IEEE, p. 61-70 10 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Clustering algorithms 100%
  26 Citations (Scopus)

• Incremental exact min-cut in poly-logarithmic amortized update time

  Goranci, G., Henzinger, M. & Thorup, M., 1 Aug 2016, 24th Annual European Symposium on Algorithms (ESA 2016). Sankowski, P. & Zaroliagis, C. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 17 p. 46. (Leibniz International Proceedings in Informatics, Vol. 57).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Polynomials 100%
  3 Citations (Scopus)

  57 Downloads (Pure)

• On the k-independence required by linear probing and minwise independence

  Pǎtraşcu, M. & Thorup, M., 2016, In: ACM Transactions on Algorithms. 12, 1, 27 p., 8.

  Research output: Contribution to journal › Journal article › Research › peer-review

  • Hash Function 100%
  • Independence 95%
  • Upper bound 35%
  • Time Constant 31%
  • Logarithmic 22%
  13 Citations (Scopus)

• The power of two choices with simple tabulation

  Dahlgaard, S., Knudsen, M. B. T., Rotenberg, E. & Thorup, M., 2016, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Krauthgamer, R. (ed.). Society for Industrial and Applied Mathematics, p. 1631-1642 12 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Hash functions 100%
  • Bins 46%
  • Resource allocation 23%
  5 Citations (Scopus)
• 2015

  Adjacency labeling schemes and induced-universal graphs

  Alstrup, S., Kaplan, H., Thorup, M. & Zwick, U., 14 Jun 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

  • Labeling Scheme 100%
  • Universal Graphs 99%
  • Adjacency 73%
  • Graph in graph theory 30%
  • Tournament 24%
  22 Citations (Scopus)

• Construction and impromptu repair of an MST in a distributed network with o(m) communication

  King, V., Kutten, S. & Thorup, M., 21 Jul 2015, Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, p. 71-80 10 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Repair 100%
  • Communication 61%
  • Telecommunication links 28%
  • Telecommunication networks 26%
  22 Citations (Scopus)

• Deterministic global minimum cut of a simple graph in near-linear time

  Kawarabayashi, K. & Thorup, M., 14 Jun 2015, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing: STOC '15. Association for Computing Machinery, p. 665-674 10 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Set theory 100%
  30 Citations (Scopus)

• From independence to expansion and back again

  Christiani, T. L., Pagh, R. & Thorup, M., 14 Jun 2015, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing: STOC '15. Association for Computing Machinery, p. 813-820 8 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Hash functions 100%
  8 Citations (Scopus)

• Hashing for statistics over k-partitions

  Dahlgaard, S., Knudsen, M. B. T., Rotenberg, E. & Thorup, M., 11 Dec 2015, Proceedings. 56th Annual Symposium on Foundations of Computer Science. IEEE, p. 1292-1310 19 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Hash functions 100%
  • Bins 93%
  • Statistics 63%
  • Set theory 27%
  • Data streams 21%
  13 Citations (Scopus)

• Planar reachability in linear space and constant time

  Holm, J., Rotenberg, E. & Thorup, M., 11 Dec 2015, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, p. 370-389 20 p. (Symposium on Foundations of Computer Science. Annual Proceedings).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Data structures 100%
  6 Citations (Scopus)

• RAM-efficient external memory sorting

  Arge, L. & Thorup, M., 1 Dec 2015, In: Algorithmica. 73, 4, p. 623-636 14 p.

  Research output: Contribution to journal › Journal article › Research › peer-review

  • External Memory 100%
  • Sorting 71%
  • Random access storage 68%
  • Internal 51%
  • Models of Computation 38%
  2 Citations (Scopus)

• Sample(x)=(a*x< =t) is a distinguisher with probability 1/8

  Thorup, M., 11 Dec 2015, Proceedings. 56th Annual Symposium on Foundations of Computer Science. IEEE, p. 1277-1291 15 p. (Symposium on Foundations of Computer Science. Annual Proceedings).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Integer 100%
  • Overflow 83%
  • Hash Function 78%
  • Random Sampling 75%
  • Probability Space 67%
• 2014

  Algorithms and estimators for summarization of unaggregated data streams

  Cohen, E., Duffield, N., Kaplan, H., Lund, C. & Thorup, M., Nov 2014, In: Journal of Computer and System Sciences. 80, 7, p. 1214-1244 31 p.

  Research output: Contribution to journal › Journal article › Research › peer-review

  10 Citations (Scopus)

• Approximately minwise independence with twisted tabulation

  Dahlgaard, S. & Thorup, M., 2014, Algorithm Theory – SWAT 2014: 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings. Ravi, R. & Gørtz, I. L. (eds.). Springer, p. 134-145 12 p. (Lecture notes in computer science, Vol. 8503).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Hashing 100%
  • Independence 68%
  • Hash Function 38%
  • Random Function 17%
  • Large Set 16%
  6 Citations (Scopus)

• Coloring 3-colorable graphs with o(n ^1/5) colors

  Kawarabayashi, K. & Thorup, M., 1 Mar 2014, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Mayr, E. W. & Portier, N. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 458-469 12 p. (Leibniz International Proceedings in Informatics, Vol. 25).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Coloring 100%
  • Color 60%
  • Computational complexity 6%
  • Polynomials 6%
  10 Citations (Scopus)

  2344 Downloads (Pure)

• Dynamic integer sets with optimal rank, select, and predecessor search

  Patrascu, M. & Thorup, M., 7 Dec 2014, FOCS 2014: 55th Annual Symposium on Foundations of Computer Science. IEEE, p. 166-175 10 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Data Structures 100%
  • Time Constant 84%
  • Integer 64%
  • Fusion 52%
  • Query 48%
  25 Citations (Scopus)

• Union-find with constant time deletions

  Alstrup, S., Thorup, M., Gørtz, I. L., Rauhe, T. & Zwick, U., 11 Aug 2014, In: A C M Transactions on Algorithms. 11, 1, 28 p., 6.

  Research output: Contribution to journal › Journal article › Research › peer-review

  • Time Constant 100%
  • Deletion 90%
  • Union 68%
  • Data Structures 32%
  • Costs 17%
  7 Citations (Scopus)
• 2013

  Bottom-k and priority sampling, set similarity and subset sums with minimal independence

  Thorup, M., 2013, STOC '13: Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing. Association for Computing Machinery, p. 371-380 10 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Subset Sum 100%
  • Hash Function 85%
  • Hashing 72%
  • Independence 61%
  • Similarity 59%
  15 Citations (Scopus)

• Funding successful research

  Thorup, M., 2013, In: Communications of the A C M. 56, 3, p. 38-39 2 p.

  Research output: Contribution to journal › Comment/debate › Research

  1 Citation (Scopus)

• Intra-domain traffic engineering with shortest path routing protocols

  Altin, A., Fortz, B., Thorup, M. & Ümit, H., Apr 2013, In: Annals of Operations Research. 204, 1, p. 56-95 40 p.

  Research output: Contribution to journal › Journal article › Research › peer-review

  • Routing Protocol 100%
  • Shortest Path 77%
  • Optimization Techniques 34%
  • Routing 30%
  • World Wide Web 18%
  21 Citations (Scopus)

• Mihai Pätrascu: obituary and open problems

  Thorup, M., 2013, In: SIGACT News. 44, 1, p. 110-114 5 p.

  Research output: Contribution to journal › Journal article › Research

• More compact oracles for approximate distances in undirected planar graphs

  Kawarabayashi, K., Sommer, C. & Thorup, M., 2013, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Khanna, S. (ed.). Association for Computing Machinery, p. 550-563 14 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Oracle 100%
  • Undirected Graph 89%
  • Planar graph 86%
  • Query 80%
  • Trade-offs 27%
  17 Citations (Scopus)

• Nearest neighbor classification using bottom-k sketches

  Dahlgaard, S., Igel, C. & Thorup, M., 2013, 2013 IEEE International Conference on Big Data: proceedings. IEEE, p. 28-34 7 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Support vector machines 100%
  • Machine learning 91%
  • Classifiers 87%
  • Hash functions 73%
  1 Citation (Scopus)

• RAM-efficient external memory sorting

  Arge, L. & Thorup, M., 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

  • Random access storage 100%
  • Sorting 89%
  • Data storage equipment 55%
  3 Citations (Scopus)

• Simple tabulation, fast expanders, double tabulation, and high independence

  Thorup, M., 2013, 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, p. 90-99 10 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Hash functions 100%
  • Chemical analysis 13%
  20 Citations (Scopus)

• Twisted tabulation hashing

  Thorup, M. & Patrascu, M., 2013, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Khanna, S. (ed.). Association for Computing Machinery, p. 209-228 20 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Online systems 100%
  • Routers 79%
  • Polynomials 63%
  • Throughput 57%
  • Internet 56%
  10 Citations (Scopus)
• 2012

  A new infinity of distance oracles for sparse graphs

  Patrascu, M., Roditty, L. & Thorup, M., 2012, 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, p. 738-747 10 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Stretch 100%
  • Sparse Graphs 98%
  • Oracle 87%
  • Infinity 56%
  • Integer 18%
  24 Citations (Scopus)

• Combinatorial coloring of 3-colorable graphs

  Kawarabayashi, K. & Thorup, M., 2012, 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. IEEE, p. 68-75 8 p.

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Coloring 100%
  • Color 60%
  • Polynomials 16%
  14 Citations (Scopus)