# Under review

C. Whidden,
R.G. Beiko,
and N. Zeh.
Fixed-parameter and approximation algorithms for maximum agreement forests
of multifurcating trees.
Submitted to

*Algorithmica*, 2013.# Journal papers

C. Whidden,
N. Zeh,
and R.G. Beiko.
Supertrees based on the subtree prune-and-regraft distance.
Accepted for publication in

*Systematic Biology*, 2014.C. Whidden,
R.G. Beiko,
and N. Zeh.
Fixed-parameter and approximation algorithms for maximum agreement forests.

*SIAM Journal on Computing*42(4):1431–1466, 2013.U. Meyer
and
N. Zeh.
I/O-efficient shortest path algorithms for undirected graphs with random and bounded edge
lengths.

*ACM Transactions on Algorithms*8(3):22, 2012.D. Ajwani,
A. Cosgaya-Lozano,
and N. Zeh.
A topological sorting algorithm for large graphs.

*ACM Journal of Experimental Algorithmics*17(1), 2012. ALENEX 2011 special issue.P. Afshani,
C. Hamilton,
and N. Zeh.
Cache-oblivious range reporting with optimal queries requires superlinear space.

*Discrete and Computational Geometry*45(4):824–850, 2011. SoCG 2009 special issue.G. Hickey,
M. Blanchette,
P. Carmi,
A. Maheshwari,
and N. Zeh.
An approximation algorithm for Noah's Ark problem with random feature loss.

*IEEE/ACM Transactions on Computational Biology and Bioinformatics*8(2):551–556, 2011.A. Maheshwari,
M. Smid,
and N. Zeh.
Low-interference networks in metric spaces with bounded doubling dimension.

*Information Processing Letters*111(23–24):1120–1123, 2011.P. Afshani,
C. Hamilton,
and N. Zeh.
A general approach for cache-oblivious range reporting and approximate range counting.

*Computational Geometry: Theory and Applications*43(8):700–712, 2010. SoCG 2009 special issue.P. Bose,
P. Carmi,
M. Couture,
A. Maheshwari,
M. Smid,
and N. Zeh.
Geometric spanners with small chromatic number.

*Computational Geometry: Theory and Applications*42(2):134–146, 2009.A. Maheshwari
and
N. Zeh.
I/O-efficient algorithms for graphs of bounded treewidth.

*Algorithmica*54(3):413–469, 2009.A. Maheshwari
and
N. Zeh.
I/O-efficient planar separators.

*SIAM Journal on Computing*38(3):767–801, 2008.A. Maheshwari,
M. Smid,
and N. Zeh.
I/O-efficient algorithms for computing planar geometric spanners.

*Computational Geometry: Theory and Applications*40(3):252–271, 2008.O. Baltzer,
A. Rau-Chaplin,
and N. Zeh.
Storage and indexing of relational OLAP views with mixed categorical and continuous dimensions.

*Journal of Digital Information Management*5(4):180–190, 2007.R. Nowakowski
and
N. Zeh.
Boundary-optimal triangulation flooding.

*International Journal on Computational Geometry and Applications*16(2–3):271–290, 2006. ISAAC 2004 special issue.S. Govindarajan,
T. Lukovszki,
A. Maheshwari,
and N. Zeh.
I/O-efficient well-separated pair decomposition and its applications.

*Algorithmica*45(4):565–614, 2006.A. Maheshwari
and
N. Zeh.
I/O-efficient algorithms for outerplanar graphs.

*Journal of Graph Algorithms and Applications*8(1):47–87, 2004.P. Bose,
A. Maheshwari,
G. Narasimham,
M. Smid,
and N. Zeh.
Approximating geometric bottleneck shortest paths.

*Computational Geometry: Theory and Applications*29(3):233–249, 2004.L. Arge,
U. Meyer,
L. Toma,
and N. Zeh.
On external-memory planar depth first search.

*Journal of Graph Algorithms and Applications*7(2):105–129, 2003.D. Hutchinson,
A. Maheshwari,
and N. Zeh.
An external memory data structure for shortest path queries.

*Discrete Applied Mathematics*126(1):55–82, 2003. COCOON 1999 special issue.# Conference papers

L. Arge,
F. van Walderveen,
and N. Zeh.
Multiway cycle separators and I/O-efficient planar graph algorithms.
In

*Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)*, pages 901–918, 2013.O. Baltzer,
A. Rau-Chaplin,
and N. Zeh.
Building a scalable spatial OLAP system.
In

*Proceedings of the 28th ACM Symposium on Applied Computing (SAC 2013)*, pages 13–15, 2013.A. Rau-Chaplin,
B. Varghese,
D. Wilson,
Z. Yao,
and N. Zeh.
QuPARA: Query-driven large-scale portfolio aggregate risk analysis on MapReduce.
In

*Proceedings of the 1st IEEE Conference on Big Data (BigData 2013)*, 2013.R. Dorrigiv,
M. He,
and N. Zeh.
On the advice complexity of buffer management.
In

*Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC 2012)*, pages 136–145, 2012.M. He,
P. Nicholson,
and N. Zeh.
A space-efficient framework for dynamic point location.
In

*Proceedings of the 23rd International Symposiun on Algorithms and Computation (ISAAC 2012)*, pages 548–557, 2012.P. Afshani
and
N. Zeh.
Lower bounds for sorted geometric queries in the I/O model.
In

*Proceedings of the 20th European Symposium on Algorithms (ESA 2012)*, pages 48–59, 2012.N. Sitchinava
and
N. Zeh.
A parallel buffer tree.
In

*Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2012)*, pages 214–223, 2012.D. Ajwani,
N. Sitchinava,
and N. Zeh.
I/O-optimal distribution sweeping on private-cache chip multiprocessors.
In

*Proceedings of the 25th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2011)*, pages 1114–1123, 2011.P. Afshani,
G.S. Brodal,
and N. Zeh.
Ordered and unordered top-K range reporting in large data sets.
In

*Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)*, pages 390–400, 2011.P. Afshani
and
N. Zeh.
Improved space bounds for cache-oblivious range reporting.
In

*Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)*, pages 1745–1758, 2011.D. Ajwani,
A. Cosgaya-Lozano,
and N. Zeh.
Engineering a topological sorting algorithm for massive graphs.
In

*Proceedings of the 13th Workshop on Algorithm Engineering and Experiments (ALENEX 2011)*, pages 139–150, 2011.D. Ajwani,
N. Sitchinava,
and N. Zeh.
Geometric algorithms for private-cache chip multiprocessors.
In

*Proceedings of the 18th European Symposium on Algorithms (ESA 2010)*, volume 6347 of*Lecture Notes in Computer Science*, pages 75–86. © Springer-Verlag, 2010.C. Whidden,
R.G. Beiko,
and N. Zeh.
Fast FPT algorithms for computing rooted agreement forests: Theory and experiments.
In

*Proceedings of the 9th International Symposium on Experimental Algorithms (SEA 2010)*, volume 6049 of*Lecture Notes in Computer Science*, pages 141–153. © Springer-Verlag, 2010. The result on computing*acyclic*agreement forests in this paper uses the wrong definition of an acyclic agreement forest and is thus incorrect. A slightly slower but correct algorithm is published in SICOMP 2013.L. Arge,
M. Revsbæk,
and N. Zeh.
I/O-efficient computation of water flow across a terrain.
In

*Proceedings of the 26th ACM Symposium on Computational Geometry (SoCG 2010)*, pages 403–412, 2010.C. Dillabaugh,
M. He,
A. Maheshwari,
and N. Zeh.
I/O and space-efficient path traversal in planar graphs.
In

*Proceedings of the 20th International Conference on Algorithms and Computation (ISAAC 2009)*, volume 5878 of*Lecture Notes in Computer Science*, pages 1175–1184. © Springer-Verlag, 2009.V. Kešelj,
H. Liu,
N. Zeh,
C. Blouin,
and C. Whidden.
Finding optimal parameters for edit distance based sequence classification is NP-hard.
In

*Proceedings of the ACM SIGKDD Workshop on Statistical an Relational Learning in Bioinformatics*, pages 17–21, 2009.C. Whidden
and
N. Zeh.
A unifying view on approximation and FPT of agreement forests.
In

*Proceedings of the 9th International Workshop on Algorithms in Bioinformatics (WABI 2009)*, volume 5724 of*Lecture Notes in Computer Science*, pages 390–402. © Springer-Verlag, 2009. The result on computing*acyclic*agreement forests in this paper uses the wrong definition of an acyclic agreement forest and is thus incorrect. A slightly slower but correct algorithm is published in SICOMP 2013.P. Afshani,
C. Hamilton,
and N. Zeh.
Cache-oblivious range reporting with optimal queries requires superlinear space.
In

*Proceedings of the 25th ACM Symposium on Computational Geometry (SoCG 2009)*, pages 277–286, 2009.P. Afshani,
C. Hamilton,
and N. Zeh.
A general approach for cache-oblivious range reporting and approximate range counting.
In

*Proceedings of the 25th ACM Symposium on Computational Geometry (SoCG 2009)*, pages 287–295, 2009.A. Cosgaya
and
N. Zeh.
A heuristic strong connectivity algorithm for large graphs.
In

*Proceedings of the 8th International Symposium on Experimental Algorithms (SEA 2009)*, volume 5526 of*Lecture Notes in Computer Science*, pages 113–124. © Springer-Verlag, 2009.P. Bose,
J. Cardinal,
S. Collette,
E.D. Demaine,
B. Palop,
P. Taslakian,
and N. Zeh.
Relaxed Gabriel graphs.
In

*Proceedings of the 21st Canadian Conference on Computational Geometry (CCCG 2009)*, pages 169–172, 2009.L. Arge,
T. Mølhave,
and N. Zeh.
Cache-oblivious red-blue line segment intersection.
In

*Proceedings of the 16th European Symposium on Algorithms (ESA 2008)*, volume 5193 of*Lecture Notes in Computer Science*, pages 88–99. © Springer-Verlag, 2008.G. Hickey,
P. Carmi,
A. Maheshwari,
and N. Zeh.
NAPX: A polynomial-time approximation scheme for Noah's Ark problem.
In

*Proceedings of the 8th International Workshop on Algorithms in Bioinformatics (WABI 2008)*, volume 5251 of*Lecture Notes in Computer Science*, pages 76–86. © Springer-Verlag, 2008.P. Bose,
P. Carmi,
M. Couture,
A. Maheshwari,
M. Smid,
and N. Zeh.
Geometric spanners with small chromatic number.
In

*Proceedings of the 5th Workshop on Approximation and Online Algorithms (WAOA 2007)*, volume 4927 of*Lecture Notes in Computer Science*, pages 75–88. © Springer-Verlag, 2007.J.-P. Deveaux,
A. Rau-Chaplin,
and N. Zeh.
Adaptive tuple differential coding.
In

*Proceedings of the 18th International Conference on Database and Expert Systems Applications (DEXA 2007)*, volume 4653 of*Lecture Notes in Computer Science*, pages 109–119. © Springer-Verlag, 2007.A. Cosgaya-Lozano,
A. Rau-Chaplin,
and N. Zeh.
Parallel computation of skyline queries.
In

*Proceedings of the 21st International Symposium on High Performance Computing Systems and Applications*, 2007.L. Allulli,
P. Lichodzijewski,
and N. Zeh.
A faster cache-oblivious shortest-path algorithm for undirected graphs with bounded edge
lengths.
In

*Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007)*, pages 910–919, 2007.A.E. Scott,
U. Stege,
and N. Zeh.
Politician's Firefighting.
In

*Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC 2006)*, volume 4288 of*Lecture Notes in Computer Science*, pages 608–617. © Springer-Verlag, 2006.U. Meyer
and
N. Zeh.
I/O-efficient undirected shortest paths with unbounded edge lengths.
In

*Proceedings of the 14th European Symposium on Algorithms (ESA 2006)*, volume 4168 of*Lecture Notes in Computer Science*, pages 540–551. © Springer-Verlag, 2006.L. Arge
and
N. Zeh.
Simple and semi-dynamic structures for cache-oblivious planar orthogonal range searching.
In

*Proceedings of the 22nd ACM Symposium on Computational Geometry (SoCG 2006)*, pages 158–166, 2006.L. Arge,
A. Danner,
H. Haverkort,
and N. Zeh.
I/O-efficient hierarchical watershed decomposition of grid terrain models.
In

*Progress in Spatial Data Handling: 12th International Symposium on Spatial Data Handling (SDH 2006)*, pages 825–844, 2006.H. Jampala
and
N. Zeh.
Cache-oblivious planar shortest paths.
In

*Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005)*, volume 3580 of*Lecture Notes in Computer Science*, pages 563–575. © Springer-Verlag, 2005.R. Nowakowski
and
N. Zeh.
Boundary-optimal triangulation flooding.
In

*Proceedings of the 15th International Symposium on Algorithms and Computation (ISAAC 2004)*, volume 3341 of*Lecture Notes in Computer Science*, pages 717–728. © Springer-Verlag, 2004.N. Zeh.
Connectivity of graphs under edge flips.
In

*Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT 2004)*, volume 3111 of*Lecture Notes in Computer Science*, pages 161–173. © Springer-Verlag, 2004.G.S. Brodal,
R. Fagerberg,
U. Meyer,
and N. Zeh.
Cache-oblivious data structures and algorithms for undirected breadth-first search and
shortest paths.
In

*Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT 2004)*, volume 3111 of*Lecture Notes in Computer Science*, pages 480–492. © Springer-Verlag, 2004.U. Meyer
and
N. Zeh.
I/O-efficient undirected shortest paths.
In

*Proceedings of the 11th European Symposium on Algorithms (ESA 2003)*, volume 2832 of*Lecture Notes in Computer Science*, pages 434–445. © Springer-Verlag, 2003.L. Arge
and
N. Zeh.
I/O-efficient strong connectivity and depth-first search for directed planar graphs.
In

*Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS 2003)*, pages 261–270, 2003.L. Arge,
L. Toma,
and N. Zeh.
I/O-efficient topological sorting of planar DAGs.
In

*Proceedings of the 15th ACM Symposium on Parallism in Algorithms and Architectures (SPAA 2003)*, pages 85–93, 2003.P. Bose,
A. Maheshwari,
G. Narasimhan,
M. Smid,
and N. Zeh.
Approximating geometric bottleneck shortest paths.
In

*Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science (STACS 2003)*, volume 2607 of*Lecture Notes in Computer Science*, pages 38–49. © Springer-Verlag, 2003.A. Maheshwari
and
N. Zeh.
I/O-optimal algorithms for planar graphs using separators.
In

*Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA 2002)*, pages 372–381, 2002.A. Maheshwari,
J. Vahrenhold,
and N. Zeh.
On reverse nearest neighbor queries.
In

*Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002)*, pages 128–132, 2002.T. Lukovszki,
A. Maheshwari,
and N. Zeh.
I/O-efficient batched range counting and its applications to proximity problems.
In

*Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2001)*, volume 2245 of*Lecture Notes in Computer Science*, pages 244–255. © Springer-Verlag, 2001.L. Arge,
U. Meyer,
L. Toma,
and N. Zeh.
On external-memory planar depth first search.
In

*Proceedings of the 7th International Workshop on Algorithms and Data Structures (WADS 2001)*, volume 2125 of*Lecture Notes in Computer Science*, pages 471–482. © Springer-Verlag, 2001.A. Maheshwari,
M. Smid,
and N. Zeh.
I/O-efficient shortest-path queries in geometric spanners.
In

*Proceedings of the 7th International Workshop on Algorithms and Data Structures (WADS 2001)*, volume 2125 of*Lecture Notes in Computer Science*, pages 287–299. © Springer-Verlag, 2001.N. Zeh
and
N. Santoro.
On finding minimum deadly sets for directed networks.
In

*Proceedings of the 8th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2001)*, pages 351–365, 2001.A. Maheshwari
and
N. Zeh.
I/O-efficient algorithms for bounded treewidth graphs.
In

*Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA 2001)*, pages 89–90, 2001.S. Govindarajan,
T. Lukovszki,
A. Maheshwari,
and N. Zeh.
I/O-efficient well-separated pair decomposition and its applications.
In

*Proceedings of the 8th European Symposium on Algorithms (ESA 2000)*, volume 1879 of*Lecture Notes in Computer Science*, pages 220–231. © Springer-Verlag, 2000.A. Maheshwari
and
N. Zeh.
External memory algorithms for outerplanar graphs.
In

*Proceedings of the 10th International Symposium on Algorithms and Computation (ISAAC 1999)*, volume 1741 of*Lecture Notes in Computer Science*, pages 307–316. © Springer-Verlag, 1999.D. Hutchinson,
A. Maheshwari,
and N. Zeh.
An external memory data structure for shortest path queries.
In

*Proceedings of the 5th Annual Combinatorics and Computing Conference (COCOON 1999)*, volume 1627 of*Lecture Notes in Computer Science*, pages 51–60. © Springer-Verlag, 1999.# Technical reports

C. Whidden,
R.G. Beiko,
and N. Zeh.

*Fixed-parameter and approximation algorithms for maximum agreement forests*. arXiv:1108.2664v1, 2011.C. Whidden,
R.G. Beiko,
and N. Zeh.

*Fast FPT algorithms for computing rooted agreement forests: Theory and experiments*. Technical Report CS-2010-03, Faculty of Computer Science, Dalhousie University, Halifax, 2010.C. Whidden
and
N. Zeh.

*A unifying view on approximation and FPT of agreement forests*. Technical Report CS-2009-02, Faculty of Computer Science, Dalhousie University, Halifax, 2009.U. Meyer
and
N. Zeh.

*I/O-efficient undirected shortest paths with unbounded edge weights*. Technical Report CS-2006-04, Faculty of Computer Science, Dalhousie University, Halifax, 2006.N. Zeh.

*Improved and more realistic algorithms for maximal graph connectivity*. Technical Report CS-2004-04, Faculty of Computer Science, Dalhousie University, Halifax, 2004.G.S. Brodal,
R. Fagerberg,
U. Meyer,
and N. Zeh.

*Cache-oblivious data structures and algorithms for undirected breadth-first search and shortest paths*. BRICS Report RS-04-2, Aarhus, Denmark, 2004.N. Zeh.

*Connectivity of graphs under edge flips*. Technical Report 2003-07, Faculty of Computer Science, Dalhousie University, Halifax, 2003.N. Zeh.

*I/O-efficient planar embedding using graph separators*. Technical Report TR-01-07, School of Computer Science, Carleton University, Ottawa, 2001.N. Zeh.

*I/O-efficient planar separators and applications*. Technical Report TR-01-02, School of Computer Science, Carleton University, Ottawa, 2001.D. Hutchinson,
A. Maheshwari,
and N. Zeh.

*An external memory data structure for shortest path queries*. Jenaer Schriften zur Mathematik und Informatik 99/11, Friedrich-Schiller-Universität Jena, 1999.N. Zeh,
J. Dietel,
and H.-D. Hecker.

*Computing the union of simple polygons in O(log n) time using O(n*. Forschungsergebnisse Math/Inf/97/12, Friedrich-Schiller-Universität Jena, 1997.^{2}) processors# Book chapters

L. Arge
and
N. Zeh.
I/O-efficient algorithms.
In M.J. Atallah
and
M. Blanton (eds.),

*Handbook of Algorithms and Theory of Computation*, 2nd edition, © CRC Press, 2009.N. Zeh.
I/O-model.
In M.-Y. Kao (ed.),

*Encyclopedia of Algorithms*, © Springer-Verlag, 2008.A. Maheshwari
and
N. Zeh.
A survey of techniques for designing I/O-efficient algorithms.
In U. Meyer, P. Sanders, and J. Sibeyn (eds.),

*Algorithms for Memory Hierarchies*, volume 2625 of*Lecture Notes in Computer Science*, pages 36–61. © Springer-Verlag, 2003.L. Toma
and
N. Zeh.
I/O-efficient algorithms for sparse graphs.
In U. Meyer, P. Sanders, and J. Sibeyn (eds.),

*Algorithms for Memory Hierarchies*, volume 2625 of*Lecture Notes in Computer Science*, pages 85–109. © Springer-Verlag, 2003.# Theses

N. Zeh.

*I/O-Efficient Algorithms for Shortest Path Related Problems*. Ph.D. thesis, School of Computer Science, Carleton University, Ottawa, Canada, 2002.N. Zeh.

*An External-Memory Data Structure for Shortest Path Queries*. Diplomarbeit, Friedrich-Schiller-Universität Jena, Germany, 1998.# Manuscripts

N. Zeh.

*I/O-efficient graph algorithms*. Lecture notes from*EEF Summer School on Massive Data Sets*, Aarhus, Denmark, 2002.