Publications

Arge, L., Brodal, G. S. & Toma, L. (2004). On External-Memory MST, SSP and Multi-Way Planar Graph Separation. Journal of Algorithms, 53(2), 186-206.

Brodal, G. S., Fagerberg, R. & Moruz, G. (2004). On the Adaptiveness of Quicksort. BRICS Report Series, (RS-04-27).

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., 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. & Farach-Colton, M. (Ed.) (2003). Lower Bounds for External Memory Dictionaries. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms (pp. 546-554). Society for Industrial and Applied Mathematics.

Brodal, G. S., Fagerberg, R. & Goemans, M. X. (Ed.) (2003). On the Limits of Cache-Obliviousness. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (pp. 307-315). Association for Computing Machinery. https://doi.org/10.1145/780542.780589

Brodal, G. S., Lagogiannis, G., Makris, C., Tsakalidis, A. & Tsichlas, K. (2003). Optimal Finger Search Trees in the Pointer Machine. Journal of Computer and System Sciences, 67(2), 381-418. https://doi.org/10.1016/S0022-0000(03)00013-8

Brodal, G. S., Fagerberg, R., Mailund, T., Pedersen, C. N. S. & Phillips, D. (2003). Speeding Up Neighbour-Joining Tree Construction. (Work package 5 ed.) ALCOM-FT.

Brodal, G. S., Fagerberg, R., Mailund, T., Pedersen, C. N. S. & Phillips, D. (2003). Speeding Up Neighbour-Joining Tree Construction.

Bender, M. A., Brodal, G. S., Fagerberg, R., Ge, D., He, S., Hu, H., Iacono, J. & López-Ortiz, A. (2003). The Cost of Cache-Oblivious Searching. In Proc. 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS): IEEE Computer Society Press, Washington D.C. (Vol. Session 6, pp. 271-282). IEEE Computer Society Press.

Brodal, G. S. & Jacob, R. (2003). Time-Dependent Networks as Models to Achieve Fast Exact Time-Table Queries. Electronic Notes in Theoretical Computer Science, 92, 3-15. https://doi.org/10.1016/j.entcs.2003.12.019

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. & 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. & Jacob, R. (2002). Dynamic Planar Convex Hull. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science: (pp. 617-626). IEEE Press. https://doi.org/10.1109/SFCS.2002.1181875

Brodal, G. S., Fagerberg, R., Bose, P. (Ed.) & Morin, P. (Ed.) (2002). Funnel Heap - A Cache Oblivious Priority Queue. In P. Bose & P. Morin (Eds.), Algorithms and Computation: 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21–23, 2002 Proceedings (pp. 219-228). Springer. https://doi.org/10.1007/3-540-36136-7_20

Brodal, G. S., Makris, C., Sioutas, S., Tsakalidis, A. K. & Tsichlas, K. (2002). Optimal Solutions for the Temporal Precedence Problem. Algorithmica, 33(4), 494-510. https://doi.org/10.1007/s00453-002-0935-z

Brodal, G. S., Lyngsø, R. B., Östlin, A. & Pedersen, C. N. S. (2002). Solving the String Statistics Problem in Time O(n log n). 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. 728-739). Springer. https://doi.org/10.1007/3-540-45465-9_62

Alstrup, S., Brodal, G. S., Gørtz, I. L. & Rauhe, T. (2002). Time and Space Efficient Multi-Method Dispatching. In M. Penttonen & E. M. Schmidt (Eds.), Algorithm Theory — SWAT 2002: 8th Scandinavian Workshop on Algorithm Theory Turku, Finland, July 3–5, 2002 Proceedings (pp. 20-29). Springer. https://doi.org/10.1007/3-540-45471-3_3

Brodal, G. S., Frigioni, D. & Marchetti-Spaccamela, A. (Eds.) (2001). Algorithm Engineering: Proceedings of 5th International Workshop on Algorithm Engineering (WAE 2001). (2141 i Lecture Notes in Computer Science ed.) Springer.

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.

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., 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.

Alstrup, S., Brodal, G. S. & Rauhe, T. (2001). Optimal Static Range Reporting in One Dimension. In Proceedings of the thirty-third annual ACM symposium on Theory of computing (pp. 476-482). Association for Computing Machinery. https://doi.org/10.1145/380752.380842

Brodal, G. S., Fagerberg, R., Pedersen, C. N. S. & Östlin, A. (2001). The Complexity of Constructing Evolutionary Trees Using Experiments. In F. Orejas, P. G. Spirakis & J. van Leeuwen (Eds.), Automata, Languages and Programming: 28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings (pp. 140-151). Springer. https://doi.org/10.1007/3-540-48224-5_12

Brodal, G. S., Fagerberg, R., Pedersen, C. N. S., Östlin, A., Orejas, F. (Ed.), Spirakis, P. G. (Ed.) & Leeuwen, J. V. (Ed.) (2001). The Complexity of Constructing Evolutionary Trees Using Experiments. In Lecture Notes In Computer Science; Vol. 2076: Proceedings of the 28th International Colloquium on Automata, Languages and Programming (2076 of Lecture Notes in Computer Science ed., Vol. 2076/2001, pp. 140-151). Springer.

Alstrup, S., Brodal, G. S., Gørtz, I. L. & Rauhe, T. (2001). Time and Space Efficient Multi-Method Dispatching. Electronic Colloquium on Computational Complexity, (ITU-TR-2001-8).

Brodal, G. S. & Jacob, R. (2001). Time-dependent Networks as Models to Achieve Fast Exact Time-table Queries. Electronic Colloquium on Computational Complexity, 92(ALCOMFT-TR-01-176).

Brodal, G. S. & Jakob, R. (2000). Dynamic Planar Convex Hull with Optimal Query Time and O(log n · log log n ) Update Time. In Algorithm Theory - SWAT 2000: 7th Scandinavian Workshop on Algorithm Theory Bergen, Norway, July 5–7, 2000 Proceedings (pp. 181-186). Springer. https://doi.org/10.1007/3-540-44985-X_7

Brodal, G. S. & Pedersen, C. N. S. (2000). Finding Maximal Quasiperiodicities in Strings. In R. Giancarlo & D. Sankoff (Eds.), Combinatorial Pattern Matching: 11th Annual Symposium, CPM 2000 Montreal, Canada, June 21–23, 2000 Proceedings (pp. 397-411). Springer. https://doi.org/10.1007/3-540-45123-4_33

Brodal, G. S. & Srinivasan, V. (2000). Improved Bounds for Dictionary Look-up with One Error. Information Processing Letters, 75(1-2), 57-59. https://doi.org/10.1016/S0020-0190(00)00079-X

Alstrup, S., Brodal, G. S. & Rauhe, T. (2000). New data structures for orthogonal range searching. In 41st Annual Symposium on Foundations of Computer Science, 2000. Proceedings. (pp. 198-207). IEEE Computer Society Press. https://doi.org/10.1109/SFCS.2000.892088

Arge, L. A., Brodal, G. S. & Toma, L. (2000). On External-Memory MST, SSSP, and Multi-way Planar Graph Separation. In Algorithm Theory - SWAT 2000: 7th Scandinavian Workshop on Algorithm Theory Bergen, Norway, July 5-7, 2000 Proceedings (pp. 709-715). Springer. https://doi.org/10.1007/3-540-44985-X_37

Alstrup, S., Brodal, G. S. & Rauhe, T. (2000). Pattern matching in dynamic texts. In D. Shmoys (Ed.), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms (pp. 819-828). Society for Industrial and Applied Mathematics.

Brodal, G. S. & Fagerberg, R. (1999). Dynamic Representations of Sparse Graphs. In F. Dehne, J.-R. Sack, A. Gupta & R. Tamassia (Eds.), Algorithms and Data Structures: 6th International Workshop, WADS’99 Vancouver, Canada, August 11–14, 1999 Proceedings (pp. 773-782). Springer. https://doi.org/10.1007/3-540-48447-7_34

Brodal, G. S., Lyngsø, R. B., Pedersen, C. N. S. & Stoye, J. (1999). Finding Maximal Pairs with Bounded Gap. In M. Crochemore & M. Paterson (Eds.), Combinatorial Pattern Matching: 10th Annual Symposium, CPM 99 Warwick University, UK, July 22–24, 1999 Proceedings (pp. 134-149). Springer. https://doi.org/10.1007/3-540-48452-3_11

Agarwal, P. K., Arge, L. A., Brodal, G. S. & Vitter, J. S. (1999). I/O-efficient dynamic point location in monotone planar subdivisions. In Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms (pp. 11-20). Association for Computing Machinery.

Brodal, G. S. (1999). Priority queues on parallel machines. Parallel Computing, 25(8), 987-1011. https://doi.org/10.1016/S0167-8191(99)00032-0

Brodal, G. S., Träff, J. L. & Zaroliagis, C. D. (1998). A Parallel Priority Queue with Constant Time Operations. Journal of Parallel and Distributed Computing, 49(1), 4-21. https://doi.org/10.1006/jpdc.1998.1425

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

Brodal, G. S. (1998). Finger search trees with constant insertion time. In Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms (pp. 540-549). Society for Industrial and Applied Mathematics.

Brodal, G. S. & Katajainen, J. (1998). Worst-case efficient external-memory priority queues. In S. Arnborg & L. Ivansson (Eds.), Algorithm Theory — SWAT'98: 6th Scandinavian Workshop on Algorithm Theory Stockholm, Sweden, July 8–10, 1998 Proceedings (pp. 107-118). Springer. https://doi.org/10.1007/BFb0054359

Brodal, G. S. (1997). Predecessor queries in dynamic integer sets. In R. Reischuk & M. Morwan (Eds.), STACS 97: 14th Annual Symposium on Theoretical Aspects of Computer Science Lübeck, Germany February 27–March 1, 1997 Proceedings (pp. 21-32). Springer. https://doi.org/10.1007/BFb0023445

Brodal, G. S. (1997). Worst Case Efficient Data Structures. Department of Computer Science, Aarhus University.

Brodal, G. S. & Husfeldt, T. (1996). A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth. Department of Computer Science, Aarhus University. BRICS Report Series No. 96-1 http://www.brics.dk/RS/96/1/BRICS-RS-96-1.pdf

Brodal, G. S. & Gasieniec, L. (1996). Approximate dictionary queries. In D. Hirschberg & G. Myers (Eds.), Combinatorial Pattern Matching: 7th Annual Symposium, CPM 96 Laguna Beach, California, June 10–12, 1996 Proceedings (pp. 65-74). Springer. https://doi.org/10.1007/3-540-61258-0_6

Brodal, G. S. & Okasaki, C. (1996). Optimal purely functional priority queues. Journal of Functional Programming, 6(6), 839-858. https://doi.org/10.1017/S095679680000201X

Brodal, G. S. (1996). Partially persistent data structures of bounded degree with constant update time. Nordic Journal of Computing, 3(3), 238-255.

Brodal, G. S. & Skyum, S. (1996). The Complexity of Computing the -ary Composition of a Binary Associative Operator. Department of Computer Science, Aarhus University. BRICS Report Series No. 96-42 http://www.brics.dk/RS/96/42/BRICS-RS-96-42.pdf

Brodal, G. S., Chaudhuri, S. & Radhakrishnan, J. (1996). The randomized complexity of maintaining the minimum. Nordic Journal of Computing, 3(4), 337-351.

Brodal, G. S. (1996). Worst-case efficient priority queues. In Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms (pp. 52-58). Society for Industrial and Applied Mathematics.

Displaying results 401 to 450 out of 451

Revised 01.09.2025

Publications

Head of research