Department of Computer Science

Aarhus University Seal
 Department of Computer Science Research Publications

Publications

Sort by: Author
Brodal, G. S. & Jørgensen, A. G. (2008). Selecting Sums in Arrays. Lecture Notes in Computer Science, 5369, 100-111. https://doi.org/10.1007/978-3-540-92182-0_12
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., Kaporis, A. C., Sioutas, S., Tsakalidis, K. & Tsichlas, K. (2009). Dynamic 3-sided Planar Range Queries with Expected Doubly Logarithmic Time. Lecture Notes in Computer Science, 5878, 193-202. https://doi.org/10.1007/978-3-642-10631-6_21
Brodal, G. S., Fagerberg, R., Greve, M. & López-Ortis, A. (2009). Online Sorted Range Reporting. Lecture Notes in Computer Science, 5878, 173-182. https://doi.org/10.1007/978-3-642-10631-6_19
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., Gfeller, B., Jørgensen, A. G. & Sanders, P. (2011). Towards optimal range medians. Theoretical Computer Science, 412(24), 2588-2601. https://doi.org/10.1016/j.tcs.2010.05.003
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
Brodal, G. S., Kejlberg-Rasmussen, C. & Truelsen, J. (2010). A Cache-Oblivious Implicit Dictionary with the Working Set Property. Lecture Notes in Computer Science, 6507, 37-48. https://doi.org/10.1007/978-3-642-17514-5_4
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., Chaudhuri, S. & Radhakrishnan, J. (1996). The randomized complexity of maintaining the minimum. Nordic Journal of Computing, 3(4), 337-351.
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. & 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. & 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. & 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. & 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. & 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. & 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. (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. & 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. (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.
Brodal, G. S. (1995). Fast meldable priority queues. In S. G. Akl, F. Dehne, J.-R. Sack & N. Santoro (Eds.), Algorithms and Data Structures: 4th International Workshop, WADS '95 Kingston, Canada, August 16–18, 1995 Proceedings (pp. 282-290). Springer. https://doi.org/10.1007/3-540-60220-8_70
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. & 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., 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
Brodal, G. S. & Tsakalidis, K. (2011). Dynamic Planar Range Maxima Queries. Lecture Notes in Computer Science, 6755 , 256-267. https://doi.org/10.1007/978-3-642-22006-7_22
Brodal, G. S., Davoodi, P. & Rao, S. S. (2012). On Space Efficient Two Dimensional Range Minimum Data Structures. Algorithmica, 63(4), 815-830. https://doi.org/10.1007/s00453-011-9499-0
Brodal, G. S., Greve, M., Pandey, V. & Satti, S. R. (2011). Integer Representations towards Efficient Counting in the Bit Probe Model. Lecture Notes in Computer Science, 6648, 206-217. https://doi.org/10.1007/978-3-642-20877-5_22
Brodal, G. S., Moruz, G. & Negoescu, A. (2012). OnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm. Lecture Notes in Computer Science, 7164, 164-175 . https://doi.org/10.1007/978-3-642-29116-6_14
Brodal, G. S., Sioutas, S., Tsakalidis, K. & Tsichlas, K. (2012). Fully Persistent B-trees. The Annual A C M - S I A M Symposium on Discrete Algorithms. Proceedings, 23, 602-614. http://delivery.acm.org.ez.statsbiblioteket.dk:2048/10.1145/2100000/2095167/p602-brodal.pdf?ip=130.225.27.190&acc=ACTIVE%20SERVICE&CFID=163115493&CFTOKEN=91446070&__acm__=1356816735_08b5a98a0788aa0b0163ee8e9fc7dce3
Brodal, G. S., Nielsen, J. A. S. & Truelsen, J. (2012). Finger Search in the Implicit Model. Lecture Notes in Computer Science, 7676, 527-536 . https://doi.org/10.1007/978-3-642-35261-4_55
Brodal, G. S., Fagerberg, R., Mailund, T., Pedersen, C. N. S. & Sand, A. (2013). Efficient Algorithms for Computing the Triplet and Quartet Distance Between Trees of Arbitrary Degree. The Annual A C M - S I A M Symposium on Discrete Algorithms. Proceedings, 24, 1814-1832. http://knowledgecenter.siam.org/0236-000098/0236-000098/1
Brodal, G. S., Davoodi, P., Lewenstein, M., Raman, R. & Rao, S. S. (2012). Two Dimensional Range Minimum Queries and Fibonacci Lattices. Lecture Notes in Computer Science, 7501, 217-228 . https://doi.org/10.1007/978-3-642-33090-2_20
Brodal, G. S., Lagogiannis, G. & Tarjan, R. E. (2012). Strict fibonacci heaps. In STOC '12 Proceedings of the 44th symposium on Theory of Computing (pp. 1177-1184 ). Association for Computing Machinery. https://doi.org/10.1145/2213977.2214082
Brodal, G. S., Brodnik, A. & Davoodi, P. (2013). The encoding complexity of two dimensional range minimum data structures. In H. L. Bodlaender & G. F. Italiano (Eds.), Algorithms – ESA 2013: 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings (pp. 229-240). Springer VS. https://doi.org/10.1007/978-3-642-40450-4_20
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
Brodal, G. S., Greve, M., Pandy, V. & Satti, S. R. (2014). Integer representations towards efficient counting in the bit probe model. Journal of Discrete Algorithms, 26(May), 34–44. https://doi.org/10.1016/j.jda.2013.11.001
Brodal, G. S., Moruz, G. & Negoescu, A. (2015). OnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm. Theory of Computing Systems, 56 (1). https://doi.org/10.1007/s00224-012-9427-y
Brodal, G. S. & Larsen, K. G. (2014). Optimal Planar Orthogonal Skyline Counting Queries. In R. Ravi & I. L. Gørtz (Eds.), Algorithm Theory – SWAT 2014: 14th Scandinavian Symposium and Workshops, Denmark. Proceedings (pp. 110-121). Springer VS. https://doi.org/10.1007/978-3-319-08404-6_10
Brodal, G. S., Sioutas, S., Tsichlas, K. & Zaroliagis, C. (2010). D2-tree: A new overlay with deterministic bounds. In O. Cheong , K.-Y. Chwa & K. Park (Eds.), Algorithms and Computation: 21st International Symposium, ISAAC 2010, Jeju, Korea, December 15-17, 2010, Proceedings, Part II (pp. 1-12). Springer VS. https://doi.org/10.1007/978-3-642-17514-5_1
Brodal, G. S., Sioutas, S., Pantazos, K. & Zaroliagis, C. D. (2015). D2-tree: A new overlay with deterministic bounds. Algorithmica, 72(3), 860-883. https://doi.org/10.1007/s00453-014-9878-4
Brodal, G. S., Nielsen, J. A. S. & Truelsen, J. (2015). Strictly Implicit Priority Queues: On the Number of Moves and Worst-Case Time. In F. Dehne, J.-R. Sack & U. Stege (Eds.), Algorithms and Data Structures: 14th International Symposium, WADS 2015, Proceedings (pp. 91-102). Springer VS. https://doi.org/10.1007/978-3-319-21840-3_8
Brodal, G. S. (2016). External Memory Three-Sided Range Reporting and Top-k Queries with Sublogarithmic Updates. In N. Ollinger & H. Vollmer (Eds.), 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) (Vol. 47, pp. 23:1-23:14). Article 23 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.STACS.2016.23
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., Sioutas, S., Tsakalidis, K. & Tsichlas, K. (2020). Fully persistent B-trees. Theoretical Computer Science, 841, 10-26. https://doi.org/10.1016/j.tcs.2020.06.027
Brodal, G. S., Fagerberg, R., Hammer, D., Meyer, U., Penschuck, M. & Tran, H. (2021). An experimental study of external memory algorithms for connected components. In D. Coudert & E. Natale (Eds.), 19th International Symposium on Experimental Algorithms, SEA 2021 (pp. 23). Article 23 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SEA.2021.23
Brodal, G. S. (2022). Priority Queues with Decreasing Keys. In P. Fraigniaud & Y. Uno (Eds.), 11th International Conference on Fun with Algorithms, FUN 2022 (pp. 8:1-8:19). Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.FUN.2022.8
Brodal, G. S., Rysgaard, C. M. & Svenning, R. (2023). External Memory Fully Persistent Search Trees. In B. Saha & R. A. Servedio (Eds.), STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing (pp. 1410-1423). Association for Computing Machinery. https://doi.org/10.1145/3564246.3585140

Displaying results 151 to 200 out of 451

Previous

1

2

3

4

5

6

7

8

9

10

Next

Head of research

Revised 01.09.2025