Publication List

Each paper is listed once in its most recent version.

Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles.

P. Bose, R. Fagerberg, A. v. Renssen, S. Verdonschot
SIAM J. Comput. 44(6): 1626-1649 (2015).

String Sorting

R. Fagerberg
Chapter in Encyclopedia of Algorithms (2nd edition) Ming-Yang Kao (ed.), DOI 10.1007/978-3-642-27848-8_408-2 (online, 6 pages), Springer 2015.

Cache-oblivious Model

R. Fagerberg
Chapter in Encyclopedia of Algorithms(2nd edition), Ming-Yang Kao (ed.), DOI 10.1007/978-3-642-27848-8_62-2 (online, 7 pages), Springer 2015.

Cache-oblivious B-Tree

R. Fagerberg
Chapter in Encyclopedia of Algorithms (2nd edition), Ming-Yang Kao (ed.), DOI 10.1007/978-3-642-27848-8_61-2 (online, 5 pages), Springer 2015.

Competitive Local Routing with Constraints.

P. Bose, R. Fagerberg, A. v. Renssen, S. Verdonschot
In Proc. 26th International Symposium on Algorithms and Computation {ISAAC}, volume 9472 of LNCS, pages 23-34. Springer Verlag, 2015.

New and Improved Spanning Ratios for Yao Graphs

L. Barba, P. Bose, M. Damian, R. Fagerberg, W.L. Keng, J. O'Rourke, A. v. Renssen, P. Taslakian, S. Verdonschot, G. Xia
JoCG 6(2): 19-53, 2015 (Also in Proc. of 30th Annual Symposium on Computational Geometry (SoCG), 2014).

Continous Yao Graphs

L. Barba, P. Bose, J.-L. D. Carufel, M. Damian, R. Fagerberg, A. v. Renssen, P. Taslakian, S. Verdonschot
In Proc. of 26th Canadian Conference on Computational Geometry (CCCG), 7 pages, 2014.

Biased Predecessor Search

P. Bose, R. Fagerberg, J. Howat, P. Morin
In Proc. of 11th Latin American Theoretical Informatics Symposium (LATIN), volume 8392 of LNCS, pages 755-764, Springer Verlag, 2014.

Algorithms for Computing the Triplet and Quartet Distances for Binary and General Trees

A. Sand, M.K. Holt, J. Johansen, R. Fagerberg, G.S. Brodal, C.N.S. Pedersen, T. Mailund
Biology - Special Issue on Developments in Bioinformatic Algorithms, 2(4):1189-1209, 2013.

On the Complexity of Reconstructing Chemical Reaction Networks

R. Fagerberg, C. Flamm, D. Merkle, P. Peters, P.F. Stadler
Mathematics in Computer Science, 7(3):275-292, 2013.

Efficient Algorithms for Computing the Triplet and Quartet Distance Between Trees of Arbitrary Degree

G.S. Brodal, R. Fagerberg, T. Mailund, C.N.S. Pedersen, A. Sand
In Proc. of 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1814-1832, 2013.

A Practical O(n log^2 n) Time Algorithm for Computing the Triplet Distance on Binary Trees

A. Sand, G.S. Brodal, R. Fagerberg, C.N.S. Pedersen, T. Mailund
BMC Bioinformatics 2013, 14(Suppl 2):S18. (Also in Proc. of 11th Asia Pacific Bioinformatics Conference (APBC), 2013.)

Towards Fair and Efficient Assignments of Students to Projects

M. Chiarandini, R. Fagerberg, S. Gualandi
In Proc. of 9th International Conference on the Practice and Theory of Automated Timetabling (PATAT), pages 388-390, 2012.

Exploring Chemistry Using SMT

R. Fagerberg, C. Flamm, D. Merkle, P. Peters
In Proc. of 18th International Conference on Principles and Practice of Constraint Programming (CP), volume 7514 of LNCS, pages 900-915, Springer Verlag, 2012.

Competitive Routing on a Bounded-Degree Plane Spanner

P. Bose, R. Fagerberg, A. v. Renssen, S. Verdonschot
In Proc. of 24th Canadian Conference on Computational Geometry (CCCG), pages 285-290, 2012.

De-amortizing Binary Search Trees

P. Bose, S. Colette, R. Fagerberg, S. Langerman
In Proc. 39th International Colloquium on Automata, Languages and Programming (ICALP), volume 7391 of LNCS, pages 121-132, Springer Verlag, 2012.

On Plane Constrained Bounded-Degree Spanners

P. Bose, R. Fagerberg, A. v. Renssen, S. Verdonschot
In Proc. 10th Latin American Theoretical Informatics Symposium (LATIN), volume 7256 of LNCS, pages 85-96. Springer Verlag, 2012.

Competitive Routing in the Half-Theta-6-Graph

P. Bose, R. Fagerberg, A. v. Renssen, S. Verdonschot
In Proc. of 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1319-1328, 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.)

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