Welcome to my home page. I am a postdoctoral fellow at the Department of Mathematics and Computer Science (IMADA), University of Southern Denmark (SDU).
Below you will find some basic information about my research interests and publications.
Work address:
I taught a seminar-style course on Efficient Graph Algorithms at IMADA from January to March, 2012.
I am on the program committee (track A) for the European Symposium on Algorithms (ESA), 2012.
My current focus is on classical algorithmic problems (such as shortest paths, min cut, and max flow) 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.
G. Borradaile, S. Pettie, and C. Wulff-Nilsen
Connectivity Oracles for Planar Graphs.
To appear at SWAT 2012.
C. Wulff-Nilsen
Approximate Distance Oracles with Improved Query Time.
arXiv:1202.2336v2 [cs.DM], March 2012.
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