Publications

Stissing, M., Pedersen, C. N. S., Mailund, T. & Brodal, G. S. (2007). Computing the Quartet Distance between Evolutionary Trees of Bounded Degree. In Proceedings of the 5th Asia-Pacific Bioinformatics Conference (APBC) (pp. 101-110)

Brodal, G. S., Fagerberg, R. & Pedersen, C. N. S. (2003). Computing the Quartet Distance Between Evolutionary Trees in Time O(n log n). Algorithmica, 38(2), 377-395. https://doi.org/10.1007/s00453-003-1065-y

Brodal, G. S., Fagerberg, R., Pedersen, C. N. S., Eades, P. (Ed.) & Takaoka, T. (Ed.) (2001). Computing the Quartet Distance Between Evolutionary Trees in Time O(n log² n). In Proceedings of Algorithms and Computation : 12th International Symposium, ISAAC 2001 (2223 of Lecture Notes in Computer Science ed., Vol. 2223/2001, pp. 731-742). Springer.

Stissing, M., Mailund, T., Pedersen, C. N. S., Brodal, G. S. & Fagerberg, R. (2007). Computing the All-Pairs Quartet Distance on a Set of Evolutionary Trees. In Proceedings of the 5th Asia-Pacific Bioinformatics Conference (APBC) (pp. 91-100)

Stissing, M., Mailund, T., Pedersen, C. S., Brodal, G. S. & Fagerberg, R. (2008). Computing the all-pairs quartet distance on a set of evolutionary trees. Journal of Bioinformatics and Computational Biology, 6(1), 37-50.

Brodal, G. S., Fagerberg, R., Östlin, A., Pedersen, C. N. S. & Rao, S. S. (2003). Computing Refined Buneman Trees in Cubic Time. In G. Benson & R. Page (Eds.), Algorithms in Bioinformatics: Third International Workshop, WABI 2003, Budapest, Hungary, September 15-20, 2003. Proceedings (pp. 259-270). Springer. https://doi.org/10.1007/978-3-540-39763-2_20

Brodal, G. S. & Pinotti, M. C. (2001). Comparator Networks for Binary Heap Construction. Theoretical Computer Science, 250(1-2), 235-245. https://doi.org/10.1016/S0304-3975(99)00137-1

Brodal, G. S. & Pinotti, M. C. (1998). Comparator networks for binary heap construction. In S. Arnborg & L. Ivansson (Eds.), Algorithm Theory — SWAT'98: 6th Scandinavian Workshop on Algorithm Theory Stockholm, Sweden, July 8–10, 1998 Proceedings (pp. 158-168). Springer. https://doi.org/10.1007/BFb0054364

Damgård, I., Larsen, K. G. & Nielsen, J. B. (2019). Communication Lower Bounds for Statistically Secure MPC, With or Without Preprocessing. In A. Boldyreva & D. Micciancio (Eds.), Advances in Cryptology – CRYPTO 2019 - 39th Annual International Cryptology Conference, Proceedings (Vol. II, pp. 61-84). Springer. https://doi.org/10.1007/978-3-030-26951-7_3

Jamalabadi, S., Schwiegelshohn, C. & Schwiegelshohn, U. (2020). Commitment and Slack for Online Load Maximization. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (pp. 339–348). Association for Computing Machinery. https://doi.org/10.1145/3350755.3400271

Green Larsen, K., Mitzenmacher, M. & Tsourakakis, C. (2020). Clustering with a faulty oracle. In Y. Huang, I. King, T.-Y. Liu & M. van Steen (Eds.), WWW '20: Proceedings of The Web Conference 2020 (pp. 2831-2834). Association for Computing Machinery. https://doi.org/10.1145/3366423.3380045

Kambach, S., Sabatini, F. M., Attorre, F., Biurrun, I., Boenisch, G., Bonari, G., Čarni, A., Carranza, M. L., Chiarucci, A., Chytrý, M., Dengler, J., Garbolino, E., Golub, V., Güler, B., Jandt, U., Jansen, J., Jašková, A., Jiménez-Alfaro, B., Karger, D. N. ... Bruelheide, H. (2023). Climate-trait relationships exhibit strong habitat specificity in plant communities across Europe. Nature Communications, 14(1), Article 712. https://doi.org/10.1038/s41467-023-36240-6

Pouteau, R., Thuiller, W., Hobohm, C., Brunel, C., Conn, B. J., Dawson, W., de Sá Dechoum, M., Ebel, A. L., Essl, F., Fragman-Sapir, O., Fristoe, T., Jogan, N., Kreft, H., Lenzner, B., Meyer, C., Pergl, J., Pyšek, P., Verkhozina, A., Weigelt, P. ... van Kleunen, M. (2021). Climate and socio-economic factors explain differences between observed and expected naturalization patterns of European plants around the world. Global Ecology and Biogeography, 30(7), 1514-1531. https://doi.org/10.1111/geb.13316

Arge, L. A., Larsen, K. G., Mølhave, T. & Walderveen, F. V. (2010). Cleaning Massive Sonar Point Clouds. In Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. GIS '10 (pp. 152-161). Association for Computing Machinery. https://doi.org/10.1145/1869790.1869815

Afshani, P., Storandt, S. & Bosch, Y. (2025). Circle-Segment Intersection Queries in Connected Geometric Graphs. In H.-L. Chen, W.-K. Hon & M.-T. Tsai (Eds.), 36th International Symposium on Algorithms and Computation (ISAAC 2025) (pp. 3:1-3:16). Article 3 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ISAAC.2025.3

Damgaard, C., Moeslund, J. E. & Wind, P. (2020). Changes in the abundance of Danish orchids over the past 30 years. Diversity, 12(6), Article 244. https://doi.org/10.3390/d12060244

Haxen, M., Raeburn, M., Afshani, P. & Karras, P. (2021). Centerpoint Query Authentication. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management (CIKM '21) (pp. 3083-3087). Association for Computing Machinery. https://doi.org/10.1145/3459637.3482072

Jørgensen, A. G., Greve, M., Larsen, K. D. & Truelsen, J. (2010). Cell Probe Lower Bounds and Approximations for Range Mode. Lecture Notes in Computer Science, 6198, 605-616. https://doi.org/10.1007/978-3-642-14165-2_51

Brodal, G. S. & Fagerberg, R. (2006). Cache-oblivious String Dictionaries. In SODA '06 Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm (pp. 581-590). Association for Computing Machinery. https://doi.org/10.1145/1109557.1109621

Brodal, G. S. (2008). Cache-Oblivious Sorting. In M.-Y. Kao (Ed.), Encyclopedia of Algorithms (Vol. 3, pp. 126-129). Springer. https://doi.org/10.1007/978-0-387-30162-4_63

Brodal, G. S., Fagerberg, R. & Jacob, R. (2002). Cache-Oblivious Search Trees via Binary Trees of Small Height. In Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms (pp. 39-48). Association for Computing Machinery.

Brodal, G. S., Fagerberg, R. & Jacob, R. (2001). Cache Oblivious Search Trees via Binary Trees of Small Height. BRICS Report Series, (RS-01-36), 1-20.

Afshani, P., Hamilton, C. & Zeh, N. (2011). Cache-Oblivious Range Reporting with Optimal Queries Requires Superlinear Space. Discrete & Computational Geometry, 45(4), 824-850. https://doi.org/10.1007/s00454-011-9347-7

Afshani, P., Hamilton, C. & Zeh, N. (2009). Cache-oblivious range reporting with optimal queries requires superlinear space. In Proceedings of the 25th annual symposium on Computational geometry (pp. 277-286). Association for Computing Machinery. https://doi.org/10.1145/1542362.1542412

Arge, L., Brodal, G. S., Fagerberg, R. & Laustsen, M. (2005). Cache-Oblivious Planar Orthogonal Range Searching and Counting. In Proceedings of the twenty-first annual symposium on Computational geometry (pp. 160-169). Association for Computing Machinery. https://doi.org/10.1145/1064092.1064119

Kejlberg-Rasmussen, C. & Brodal, G. S. (2012). Cache-Oblivious Implicit Predecessor Dictionaries with the Working-Set Property. Leibniz International Proceedings in Informatics, 14, 112--123. https://doi.org/10.4230/LIPIcs.STACS.2012.112

Brodal, G. S., Demaine, E. D., Fineman, J. T., Iacono, J., Langerman, S. & Munro, J. I. (2010). Cache-Oblivious Dynamic Dictionaries with Optimal Update/Query Tradeoff. Annual A C M - S I A M Symposium on Discrete Algorithms. Proceedings, 1448-1456. http://www.siam.org/proceedings/soda/2010/SODA10_117_brodalg.pdf

Brodal, G. S. & Fagerberg, R. (2002). Cache Oblivious Distribution Sweeping. In P. Widmayer, S. Eidenbenz, F. Triguero, R. Morales, R. Conejo & M. Hennessy (Eds.), Automata, Languages and Programming: 29th International Colloquium, ICALP 2002 Málaga, Spain, July 8–13, 2002 Proceedings (pp. 426-438). Springer. https://doi.org/10.1007/3-540-45465-9_37

Brodal, G. S., Fagerberg, R., Meyer, U. & Zeh, N. (2004). Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths. In T. Hagerup & J. Katajainen (Eds.), Algorithm Theory - SWAT 2004: 9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, July 8-10, 2004. Proceedings (pp. 480-492). Springer. https://doi.org/10.1007/978-3-540-27810-8_41

Arge, L., Brodal, G. S. & Fagerberg, R. (2005). Cache-Oblivious Data Structures. In D. Mehta & S. Sahni (Eds.), Handbook of Data Structures and Applications CRC Press.

Brodal, G. S. & Mampentzidis, K. (2017). Cache oblivious algorithms for computing the triplet distance between trees. In K. Pruhs & C. Sohler (Eds.), 25th European Symposium on Algorithms, ESA 2017 (Vol. 87, pp. 21:1--21:14). Article 21 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ESA.2017.21

Brodal, G. S. (2004). Cache-Oblivious Algorithms and Data Structures. In T. Hagerup & J. Katajainen (Eds.), Algorithm Theory - SWAT 2004: 9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, July 8-10, 2004. Proceedings (pp. 3-13). Springer. https://doi.org/10.1007/978-3-540-27810-8_2

Brodal, G. S., Fagerberg, R. & Moruz, G. (2005). Cache-Aware and Cache-Oblivious Adaptive Sorting. In L. Caires, G. F. Italiano, L. Monteiro, C. Palamidessi & M. Yung (Eds.), Automata, Languages and Programming: 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005. Proceedings (pp. 576-588). Springer. https://doi.org/10.1007/11523468_47

Brodal, G. S., Rysgaard, C. M. & Svenning, R. (2025). Buffered Partially-Persistent External-Memory Search Trees. In A. Benoit, H. Kaplan, S. Wild, S. Wild & G. Herman (Eds.), 33rd Annual European Symposium on Algorithms, ESA 2025 Article 82 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ESA.2025.82

Damgård, I. B., Larsen, K. G. & Yakoubov, S. (2021). Broadcast secret-sharing, bounds and applications. In S. Tessaro (Ed.), 2nd Conference on Information-Theoretic Cryptography, ITC 2021 Article 10 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ITC.2021.10

Viallat, V. C. A., Grandoni, F., Lee, E. & Schwiegelshohn, C. (2023). Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median. In Thirty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023) (Vol. 1, pp. 940-986). Association for Computing Machinery.

Brodal, G. S. (2024). Bottom-Up Rebalancing Binary Search Trees by Flipping a Coin. In A. Z. Broder & T. Tamir (Eds.), 12th International Conference on Fun with Algorithms, FUN 2024 Article 6 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.FUN.2024.6

Brodal, G. S. (2025). Bottom-up rebalancing binary search trees by flipping a coin. Theoretical Computer Science, 1055, Article 115543. https://doi.org/10.1016/j.tcs.2025.115543

da Cunha, A., Larsen, K. G. & Ritzert, M. (2025). Boosting, Voting Classifiers and Randomized Sample Compression Schemes. In G. Kamath & P. L. Loh (Eds.), Proceedings of Machine Learning Research (Vol. 272, pp. 390-404). MLResearch Press.

Ejrnæs, R., Petersen, A. H., Bladt, J., Bruun, H. H., Moeslund, J. E., Wiberg-Larsen, P. & Rahbek, C. (2014). Biodiversitetskort for Danmark: Udviklet i samarbejde mellem Center for Makroøkologi, Evolution og Klima på Københavns Universitet og Institut for Bioscience ved Aarhus Universitet. Aarhus University, DCE - Danish Centre for Environment and Energy. Videnskabelig rapport fra DCE - Nationalt Center for Miljø og Energi No. 112

Ejrnæs, R., Bladt, J., Moeslund, J. E. & Brunbjerg, A. K. (2021). Biodiversitetskortets bioscore. Aarhus University, DCE - Danish Centre for Environment and Energy. Videnskabelig rapport fra DCE - Nationalt Center for Miljø og Energi No. 456

Chan, T. M. & Wilkinson, B. T. (2011). Bichromatic Line Segment Intersection Counting in O(n sqrt{log n}) Time. Paper presented at Canadian Conference on Computational Geometry, Canada. http://www.cccg.ca/proceedings/2011/papers/paper83.pdf

Fandina, O. N., Høgsgaard, M. M. & Larsen, K. G. (2023). Barriers for Faster Dimensionality Reduction. In P. Berenbrink, P. Bouyer, A. Dawar & M. M. Kante (Eds.), 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023 Article 31 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.STACS.2023.31

Larsen, K. G. (2024). Bagging is an Optimal PAC Learner (Extended Abstract). In K. Larson (Ed.), Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24) (pp. 8411-8415). IJCAI Organization. https://doi.org/10.24963/ijcai.2024/932

Larsen, K. G. (2023). Bagging is an Optimal PAC Learner. In G. Neu & L. Rosasco (Eds.), Proceedings of COLT 2023 (Vol. 195, pp. 450-468). MLResearch Press.

Cohen-Addad, V., Draganov, A., Russo, M., Saulpic, D. & Schwiegelshohn, C. (2025). A Tight VC-Dimension Analysis of Clustering Coresets with Applications. In Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025 (pp. 4783-4808). Association for Computing Machinery.

Brodal, G. S. (2013). A Survey on Priority Queues. In A. Brodnik, A. López-Ortiz, V. Raman & A. Viola (Eds.), Space-Efficient Data Structures, Streams, and Algorithms: Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday (pp. 150-163 ). Springer VS. https://doi.org/10.1007/978-3-642-40273-9_11

Sporbert, M., Bruelheide, H., Seidler, G., Keil, P., Jandt, U., Austrheim, G., Biurrun, I., Campos, J. A., Čarni, A., Chytrý, M., Csiky, J., De Bie, E., Dengler, J., Golub, V., Grytnes, J.-A., Indreica, A., Jansen, F., Martin Jiroušek, M., Lenoir, J. ... Welk, E. (2019). Assessing sampling coverage of species distribution in biodiversity databases. Journal of Vegetation Science, 30(4), 620-632. https://doi.org/10.1111/jvs.12763

Brodal, G. S. (2025). A Simple Integer Successor-Delete Data Structure. In P. Mutzel & N. Prezza (Eds.), 23rd International Symposium on Experimental Algorithms, SEA 2025 Article 8 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SEA.2025.8

Berglin, E. & Brodal, G. S. (2020). A Simple Greedy Algorithm for Dynamic Graph Orientation. Algorithmica, 82(2), 245-259. https://doi.org/10.1007/s00453-018-0528-0

Displaying results 351 to 400 out of 452

Revised 01.09.2025

Publications

Head of research