Publication List

Each paper is listed once in its most recent version.

On Plane Constrained Bounded-Degree Spanners

P. Bose, R. Fagerberg, A. v. Renssen, S. Verdonschot
To appear in Proc. of 10th Latin American Theoretical INformatics Symposium (LATIN), 2012.

Competitive Routing in the Half-Theta-6-Graph

P. Bose, R. Fagerberg, A. v. Renssen, S. Verdonschot
To appear in Proc. of 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012.

The Cost of Cache-Oblivious Searching

M. A. Bender, G. S. Brodal, R. Fagerberg, D. Ge, S. He, H. Hu, J. Iacono, A. López-Ortiz
Algorithmica, 61(2):463-505, 2011. (Also in Proc. 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2003.)

An O(log log n)-Competitive Binary Search Tree with Optimal Worst-Case Access Times

P. Bose, K. Douïeb, V. Dujmović, R. Fagerberg
In Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), volume 6139 of LNCS, pages 38-49. Springer Verlag, 2010.

Optimal Sparse Matrix Dense Vector Multiplication in the I/O-Model

M. A. Bender, G. S. Brodal, R. Fagerberg, R. Jacob, E. Vicari
Theory of Computing Systems (special issue on SPAA 2007), 47(4):934-962, 2010. (Also in Proc. 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2007.)

Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts

P. Bille, R. Fagerberg, I. L. Gørtz
ACM Transactions on Algorithms, Vol. 6, No. 1, Article 3, pages 1--14. ACM, 2009. (Also in Proc. 18th Annual Symposium on Combinatorial Pattern Matching (CPM), 2007.)

Online Sorted Range Reporting

G. S. Brodal, R. Fagerberg, M. Greve, A. López-Ortiz
In Proc. 20th Annual International Symposium on Algorithms and Computation (ISAAC), volume 5878 of LNCS, pages 173-182. Springer Verlag, 2009.

On the Adaptiveness of Quicksort

G. S. Brodal, R. Fagerberg, G. Moruz
ACM Journal of Experimental Algorithmics, 12, Article no. 3.2. ACM, 2008. (Also in Proc. ALENEX'05, 2005.)

String Sorting

R. Fagerberg
Chapter in Encyclopedia of Algorithms, Ming-Yang Kao (ed.), pages 907-910, Springer 2008.

Cache-oblivious Model

R. Fagerberg
Chapter in Encyclopedia of Algorithms, Ming-Yang Kao (ed.), pages 123-126, Springer 2008.

Cache-oblivious B-Tree

R. Fagerberg
Chapter in Encyclopedia of Algorithms, Ming-Yang Kao (ed.), pages 121-123, Springer 2008.

Computing the All-Pairs Quartet Distance on a set of Evolutionary Trees

M. Stissing, T. Mailund, C. N. S. Pedersen, G. S. Brodal, R. Fagerberg
Journal of Bioinformatics and Computational Biology, 6(1):37-50, 2008. (Also in Proc. 5th Asia Pacific Bioinformatics Conference (APBC), 2007.)

Optimal Resilient Dynamic Dictionaries

G. S. Brodal, R. Fagerberg, I. Finocchi, F. Grandoni, G. Italiano, A. G. Jørgensen, G. Moruz, T. Mølhave
In Proc. of 15th Annual European Symposium on Algorithms (ESA), 2007.

Engineering a Cache-Oblivious Sorting Algorithm

G. S. Brodal, R. Fagerberg, K. Vinther
ACM J. Experimental Algorithmics, Special Issue of ALENEX 2004, volume 12, Article no. 2.2. ACM 2007.

Computing the Quartet Distance Between Evolutionary Trees of Bounded Degree

M. Stissing, C. N. S. Pedersen, T. Mailund, G. S. Brodal, R. Fagerberg
In Proc. 5th Asia Pacific Bioinformatics Conference (APBC), 2007.

Recrafting the Neighbour-Joining Method

G. S. Brodal, R. Fagerberg, T. Mailund, C. N. S. Pedersen, D. Phillips
BMC Bioinformatics, 7(29), 8 pages, 2006.

External String Sorting: Faster and Cache-Oblivious

R. Fagerberg, A. Pagh, R. Pagh
In Proc. of 23rd International Symposium on Theoretical Aspects of Computer Science (STACS), 2006.

Cache-Oblivious String Dictionaries

G. S. Brodal, R. Fagerberg
In Proc. of 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006.

Cache-Aware and Cache-Oblivious Adaptive Sorting

G. S. Brodal, R. Fagerberg, G. Moruz
In Proc. 32nd International Colloquium on Automata, Languages, and Programming (ICALP), 2005.

Cache-Oblivious Planar Orthogonal Range Searching and Counting

L. Arge, G. S. Brodal, R. Fagerberg, M. Laustsen
In Proc. 21st Annual ACM Symposium on Computational Geometry (SoCG), 2005.

Balanced Binary Search Trees

A. Andersson, R. Fagerberg, K. S. Larsen
Chapter 10 in Handbook of Data Structures, CRC Press, 2005.

Cache-Oblivious Data Structures

L. Arge, G. S. Brodal, R. Fagerberg
Chapter 34 in Handbook of Data Structures, CRC Press, 2005.

Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths

G. S. Brodal, R. Fagerberg, U. Meyer, Norbert Zeh
In Proc. Algorithm Theory - SWAT 2004, pages 480-492, 2004. (Also technical report BRICS-RS-04-2, Department of Computer Science, University of Aarhus, February 2004.)

Computing the quartet distance between evolutionary trees in time O(n log n)

G. S. Brodal, R. Fagerberg, C. N. S. Pedersen
Algorithmica, 38(2):377--395, 2004.

Computing Refined Buneman Trees in Cubic Time

G. S. Brodal, R. Fagerberg, A. Östlin, C. N. S. Pedersen, and S. Rao
In Proc. 3rd Workshop on Algorithms in Bioinformatics (WABI), volume 2812 of LNCS, pages 259-270. Springer Verlag, 2003.

On the Limits of Cache-Obliviousness

G. S. Brodal, R. Fagerberg
In Proc. 35th Annual ACM Symposium on Theory of Computing (STOC), pages 307-315, 2003.

Lower bounds for external memory dictionaries

G. S. Brodal, R. Fagerberg
In Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 546-554, 2003.

Funnel Heap - A Cache Oblivious Priority Queue

G. S. Brodal, R. Fagerberg
In Proc. 13th Annual International Symposium on Algorithms and Computation (ISAAC), volume 2518 of LNCS, pages 219-228. Springer Verlag, 2002.

Cache oblivious distribution sweeping

G. S. Brodal, R. Fagerberg
In Proc. International Colloquium on Automata, Languages and Programming (ICALP) 2002, volume 2380 of LNCS, pages 426-438. Springer Verlag, Berlin, 2002.

Cache-oblivious search trees via trees of small height

G. S. Brodal, R. Fagerberg, R. Jacob
In Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 39-48, 2002.

Computing the quartet distance between evolutionary trees in time O(n log² n)

G. S. Brodal, R. Fagerberg, C. N. S. Pedersen
In Proc. 12th Annual International Symposium on Algorithms and Computation (ISAAC), volume 2223 of LNCS, pages 731-742. Springer Verlag, 2001.

Search trees with relaxed balance and near-optimal height

R. Fagerberg, K. S. Larsen, R. E. Jensen
In Proc. 7th International Workshop on Algorithms and Data Structures (WADS), volume 2125 of LNCS, pages 414-425. Springer Verlag, Berlin, 2001.

The complexity of constructing evolutionary trees using experiments

G. S. Brodal, R. Fagerberg, C. N. S. Pedersen, A. Östlin
In Proc. International Colloquium on Automata, Languages and Programming (ICALP) 2001, volume 2076 of LNCS, pages 140-151. Springer Verlag, Berlin, 2001.

The complexity of rebalancing a binary search tree

R. Fagerberg
In Proc. 19th conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS), volume 1738 of LNCS, pages 72-83. Springer Verlag, Berlin, 1999.

Dynamic representations of sparse graphs

G. S. Brodal, R. Fagerberg
In Proc. 6th International Workshop on Algorithms and Data Structures (WADS), volume 1663 of LNCS, pages 342-351. Springer Verlag, Berlin, 1999.

Amortization results for chromatic search trees, with an application to priority queues

J. Boyar, R. Fagerberg, K. S. Larsen
Journal of Computer and System Sciences, 55(3):504-521, Dec. 1997. (Also in Proc. WADS'95.)

Search Trees and Priority Queues: Closing Some Gaps

R. Fagerberg
Ph.D-thesis, Department of Computer Science, Odense University, Jan. 1997.

Binary search trees: How low can you go?

R. Fagerberg
In 5th Scandinavian Workshop on Algorithm Theory (SWAT), volume 1097 of LNCS, pages 428-439. Springer, 1996.

A generalization of binomial queues

R. Fagerberg
Information Processing Letters, 57(2):109-114, 1996.

A note on worst case efficient meldable priority queues

R. Fagerberg
Technical Report PP-1996-12, Department of Mathematics and Computer Science, Odense University, June 1 1996.

Efficient rebalancing of B-trees with relaxed balance

K. S. Larsen, R. Fagerberg
International Journal of Foundations of Computer Science, 7(2):169-186, 1996. (Also in Proc. 9th International Parallel Processing Symposium (IPPS), 1995.)