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(n2) processors. Forschungsergebnisse Math/Inf/97/12, Friedrich-Schiller-Universität Jena, 1997.

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.