Online availability of papers is on my todo-list. In the meantime,
just drop me a mail at rolf@imada.sdu.dk, and I'll send a copy.
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 log2 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.)
Rolf Fagerberg
(rolf@imada.sdu.dk)