Christian Wulff-Nilsen

Welcome to my home page. I am assistant professor at the Department of Computer Science, University of Copenhagen (DIKU). Below you will find some basic information about my research interests and publications.

How to reach me
Teaching
Program Committee
Research Interests
Publications

How to reach me

Work address:

Department of Computer Science
University of Copenhagen
Universitetsparken 5
DK-2100 Copenhagen
Denmark
Office: S25
E-mail: koolooz@di.ku.dk

Teaching

Seminar-style course on Efficient Graph Algorithms at IMADA from January to March, 2012.
Computability and Complexity, DIKU, block 2, 2012/2013.
Algorithms and Data Structures, DIKU, block 4, 2013.
Advanced Algorithms and Data Structures, DIKU, block 4, 2013.
Topics in Algorithms and Data Structures, DIKU, block 4, 2013.
Computability and Complexity, DIKU, block 2, 2013/2014.
Computational Geometry, DIKU, block 3, 2014.
Algorithms and Data Structures, DIKU, block 4, 2014.
Advanced Algorithms and Data Structures, DIKU, block 4, 2014.
Topics in Algorithms and Data Structures, DIKU, block 4, 2014.

Program Committee Work

Program committee member, European Symposium on Algorithms (ESA), track A, 2012.
Program committee member, Symposium on Discrete Algorithms (SODA), 2013.

Research Interests

My current focus is on classical algorithmic problems (such as shortest paths, min cut, max flow, and dynamic connectivity) for general graphs as well as for graphs with a fixed excluded minor, in particular planar graphs. I have previously been working on metric space and geometric (Euclidean and fixed orientations) graph problems, mainly the Steiner tree and dilation/stretch factor problems.

Publications

J. Holm, E. Rotenberg, and C. Wulff-Nilsen Faster Fully-Dynamic Minimum Spanning Forest.
arXiv:1407.6832 [cs.DS], July 2014.

C. Wulff-Nilsen Faster Separators for Shallow Minor-Free Graphs via Dynamic Approximate Distance Oracles.
arXiv:1407.6869 [cs.DS], July 2014, July 2014. Full version of the ICALP'14 paper.

C. Wulff-Nilsen Faster Separators for Shallow Minor-Free Graphs via Dynamic Approximate Distance Oracles.
ICALP 2014, pp. 1063-1074.

C. Wulff-Nilsen Faster Deterministic Fully-Dynamic Graph Connectivity.
Proc. Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, 2013.

C. Wulff-Nilsen Approximate Distance Oracles with Improved Query Time.
Proc. Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, 2013.

J. Łącki, Y. Nussbaum, P. Sankowski, and C. Wulff-Nilsen Single Source - All Sinks Max Flows in Planar Digraphs.
Proc. 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), New Brunswick, 2012.

J. Łącki, Y. Nussbaum, P. Sankowski, and C. Wulff-Nilsen Single Source - All Sinks Max Flows in Planar Digraphs.
arXiv:1210.4811v1 [cs.DM], October 2012.

C. Wulff-Nilsen Approximate Distance Oracles with Improved Query Time.
arXiv:1202.2336v3 [cs.DM], October 2012.

C. Wulff-Nilsen Faster Deterministic Fully-Dynamic Graph Connectivity.
arXiv:1209.5608 [cs.DS], September 2012.

G. Borradaile, S. Pettie, and C. Wulff-Nilsen Connectivity Oracles for Planar Graphs.
F. V. Fomin and P. Kaski (Eds.): SWAT 2012, LNCS 7357, pp. 316-327, 2012.

G. Borradaile, S. Pettie, and C. Wulff-Nilsen Connectivity Oracles for Planar Graphs.
arXiv:1204.4159v2 [cs.DS], April 2012 (extended abstract).

C. Wulff-Nilsen Approximate Distance Oracles with Improved Preprocessing Time.
Proc. Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Kyoto, 2012, pp. 202-208.

C. Wulff-Nilsen Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications.
Proc. 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), Palm Springs, 2011.

G. Borradaile, P. Klein, S. Mozes, Y. Nussbaum, and C. Wulff-Nilsen Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time.
Proc. 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), Palm Springs, 2011.

C. Wulff-Nilsen Approximate Distance Oracles with Improved Preprocessing Time.
arXiv:1109.4156v1 [cs.DM], September 2011.

C. Wulff-Nilsen Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications.
arXiv:1107.1292v1 [cs.DM], July 2011.

G. F. Italiano, Y. Nussbaum, P. Sankowski, and C. Wulff-Nilsen Improved Algorithms for Min Cut and Max Flow in Undirected Planar Graphs.
Proc. 43rd ACM Symposium on Theory of Computing (STOC), San Jose, 2011.

G. Borradaile, P. Klein, S. Mozes, Y. Nussbaum, and C. Wulff-Nilsen Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time.
arXiv:1105:2228v1 [cs.DM], May 2011.

C. Wulff-Nilsen Computing the Maximum Detour of a Plane Geometric Graph in Subquadratic Time.
Journal of Computational Geometry, Vol. 1, No. 1 (2010).

C. Wulff-Nilsen Faster Shortest Path Algorithm for H-Minor Free Graphs with Negative Edge Weights.
arXiv:1008.1048v2 [cs.DM], October 2010.

C. Wulff-Nilsen Min st-Cut of a Planar Graph in O(nloglog n) Time.
arXiv:1007.3609v2 [cs.DM], October 2010.

G. Borradaile and C. Wulff-Nilsen Multiple source, single sink maximum flow in a planar graph.
arXiv:1008.4966v1 [cs.DM], August 2010 (preliminary version).

G. Borradaile, P. Sankowski, and C. Wulff-Nilsen Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time.
Proc. 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), Las Vegas, 2010.

S. Mozes and C. Wulff-Nilsen Shortest Paths in Planar Graphs with Real Lengths in O(nlog2n/loglog n) Time.
Proc. 18th Annual European Symposium on Algorithms (ESA), Liverpool, 2010 (best student paper award).

C. Wulff-Nilsen Bounding the Expected Number of Rectilinear Full Steiner Trees.
Networks, Volume 56, Issue 1, pages 1-10, August 2010.

C. Wulff-Nilsen Constant Time Distance Queries in Planar Unweighted Graphs with Subquadratic Preprocessing Time.
Computational Geometry, special issue on the 25th European Workshop on Computational Geometry (to appear).

G. Borradaile, P. Sankowski, and C. Wulff-Nilsen Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time.
arXiv:1003.1320v2 [cs.DM], April 2010.

C. Wulff-Nilsen Algorithms for Planar Graphs and Graphs in Metric Spaces.
Ph.D. thesis, March 2010.

C. Wulff-Nilsen Computing the dilation of edge-augmented graphs in metric spaces.
Computational Geometry, Volume 43, Issue 2, February 2010, Pages 68-72, Special Issue on the 24th European Workshop on Computational Geometry.

C. Wulff-Nilsen Solving the Replacement Paths Problem for Planar Directed Graphs in O(nlogn) Time.
In proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), p. 756-765, 2010.

C. Wulff-Nilsen Minimum Cycle Basis and All-Pairs Min Cut of a Planar Graph in Subquadratic Time.
arXiv:0912.1208v1 [cs.DM], December 2009.

S. Mozes and C. Wulff-Nilsen Shortest Paths in Planar Graphs with Real Lengths in O(nlog2n/loglog n) Time.
arXiv:0911.4963v1 [cs.DM], November 2009.

C. Wulff-Nilsen Girth of a Planar Digraph with Real Edge Weights in O(nlog3n) Time.
arXiv:0908.0697v1 [cs.DM], August 2009.

C. Wulff-Nilsen Solving the Replacement Paths Problem for Planar Directed Graphs in O(nlogn) Time.
Technical Report 09-03, Department of Computer Science, University of Copenhagen, 2009.

C. Wulff-Nilsen Wiener Index and Diameter of a Planar Graph in Subquadratic Time.
Proc. 25th European Workshop on Computational Geometry, Brussels, 2009, p. 25-28.

C. Wulff-Nilsen Wiener Index, Diameter, and Stretch Factor of a Weighted Planar Graph in Subquadratic Time.
Technical Report 08-16, Department of Computer Science, University of Copenhagen, 2008.

C. Wulff-Nilsen Sum of All-Pairs Shortest Path Distances in a Planar Graph in Subquadratic Time.
Technical Report 08-11, Department of Computer Science, University of Copenhagen, 2008.

C. Wulff-Nilsen Computing the Maximum Detour of a Plane Graph in Subquadratic Time.
In S.-H. Hong, H. Nagamochi, and T. Fukunaga (Eds.): ISAAC 2008, LNCS 5369, pp. 740-751, 2008.

J. Luo and C. Wulff-Nilsen Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces.
In S.-H. Hong, H. Nagamochi, and T. Fukunaga (Eds.): ISAAC 2008, LNCS 5369, pp. 764-775, 2008.

C. Wulff-Nilsen Computing the Stretch Factor of Paths, Trees, and Cycles in Weighted Fixed Orientation Metrics.
Proc. 20th Canadian Conference on Computational Geometry (CCCG 2008), Montreal, 2008, p. 59-62.
(full version, 12 pages)

C. Wulff-Nilsen Computing the Maximum Detour of a Plane Graph in Subquadratic Time.
Technical Report 08-07, Department of Computer Science, University of Copenhagen, 2008.

C. Wulff-Nilsen Steiner hull algorithm for the uniform orientation metrics.
Computational Geometry - Theory and Applications, Vol. 40/1, May 2008, pp. 1-13.

M. Brazil, B. K. Nielsen, D. A. Thomas, P. Winter, C. Wulff-Nilsen, and M. Zachariasen. A Novel Approach to Phylogenetic Trees: d-Dimensional Geometric Steiner Trees.
Networks, volume 53, issue 2, pages 104-111, 2008.

C. Wulff-Nilsen Computing the Dilation of Edge-Augmented Graphs in Metric Spaces.
Proc. 24th European Workshop on Computational Geometry, Nancy, 2008, p. 123-126.

C. Wulff-Nilsen A linear bound on the expected number of rectilinear full Steiner tree components spanning a fixed number of terminals.
Proc. 23rd European Workshop on Computational Geometry, Graz, 2007, p. 158-161.

C. Wulff-Nilsen Proximity structures in the fixed orientation metrics.
Proc. 22nd European Workshop on Computational Geometry, Delphi, 2006, p. 153-157