Welcome to my home page. I am associate professor at the Department of Computer Science, University of Copenhagen (DIKU).
Below you will find some basic information about my teaching activities, research interests, and publications.
Work address:
Seminar-style course on Efficient Graph Algorithms at IMADA from January to March, 2012.
Computability and Complexity, DIKU, 2012-2021 (course organizer).
Algorithms and Data Structures, DIKU, 2013-present (course organizer).
Advanced Algorithms and Data Structures, DIKU, 2013-present.
Topics in Algorithms and Data Structures, DIKU, 2013-2017.
Computational Geometry, DIKU, block 3, 2014.
Randomized Algorithms, DIKU, block 2, 2014-2018.
Randomiserede Algoritmer til Dataanalyse, DIKU, block 4, 2020-present (course organizer).
Program committee member, European Symposium on Algorithms (ESA), track A, 2012.
Program committee member, Symposium on Discrete Algorithms (SODA), 2014.
Program committee member, Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2016.
Program committee member, Foundations of Computer Science (FOCS), 2018.
Program committee member, European Symposium on Algorithms (ESA), track A, 2018.
Program committee member, Symposium on Theory of Computing (STOC), 2020.
Program committee member, Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2020.
Program committee member, Symposium on Discrete Algorithms (SODA), 2021.
Program committee member, Symposium on Simplicity in Algorithms (SOSA), 2022.
Program comittee member, International Colloquium on Automata, Languages and Programming (ICALP), 2022.
Program comittee member, Highlights of Algorithms (HALG), 2022.
Editor, SIAM Journal of Computing.
My current focus is on classical algorithmic graph problems (such as shortest paths, min cut, max flow, and dynamic connectivity) in the static and in dynamic settings 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.
A. Bernstein, D. Nanongkai, and C. Wulff-Nilsen.
Negative-Weight Single-Source Shortest Paths in Almost-linear Time.
To appear at FOCS 2022 (best paper award).
P. Charalampopoulos, P. Gawrychowski, Y. Long, S. Mozes, S.
Pettie, O. Weimann, and C. Wulff-Nilsen.
Almost Optimal Exact Distance Oracles for Planar Graphs.
To appear in Journal of the ACM.
A. Bernstein, D. Nanongkai, and C. Wulff-Nilsen.
Negative-Weight Single-Source Shortest Paths in Almost-linear Time.
CoRR abs/2203.03456, 2022.
S. Alstrup, S. Dahlgaard, A. Filtser, M. Stöckel, and C. Wulff-Nilsen.
Constructing light spanners deterministically in near-linear time.
Theor. Comput. Sci. 907: 82-112, 2022.
D. Das, M. P. Gutenberg, and C. Wulff-Nilsen.
A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs.
SODA 2022.
D. Das, M. P. Gutenberg, E. Kipouridis, and C. Wulff-Nilsen.
A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs.
SOSA 2022.
H. V. Le and C. Wulff-Nilsen.
Optimal Approximate Distance Oracles for Planar Graphs.
FOCS 2021.
V. Fredslund-Hansen, S. Mozes, and C. Wulff-Nilsen.
Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs.
ISAAC 2021.
J. Evald, V. Fredslund-Hansen, and C. Wulff-Nilsen.
Near-Optimal Distance Oracles for Vertex-Labeled Planar Graphs.
ISAAC 2021.
J. Evald, V. Fredslund-Hansen, M. P. Gutenberg, and C. Wulff-Nilsen.
Decremental APSP in Unweighted Digraphs Versus an Adaptive Adversary.
ICALP 2021: 64:1-64:20.
A. Bernstein, M. P. Gutenberg, and C. Wulff-Nilsen.
Near-Optimal Decremental SSSP in Dense Weighted Digraphs.
FOCS 2020.
A. Bernstein, M. P. Gutenberg, and C. Wulff-Nilsen.
Near-Optimal Decremental SSSP in Dense Weighted Digraphs.
CoRR abs/2004.04496, 2020.
M. Abrahamsen, J. Holm, E. Rotenberg, and C. Wulff-Nilsen.
Escaping an Infinitude of Lions.
Am. Math. Mon. 127(10): 880-896, 2020.
V. Fredslund-Hansen, S. Mozes, and C. Wulff-Nilsen.
Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs.
CoRR abs/2009.14716, 2020.
J. Evald, V. Fredslund-Hansen, M. P. Gutenberg, and C. Wulff-Nilsen.
Decremental APSP in Directed Graphs Versus an Adaptive Adversary.
CoRR abs/2010.00937, 2020.
M. P. Gutenberg and C. Wulff-Nilsen.
Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds.
SODA 2020: 2562-2574.
M. P. Gutenberg and C. Wulff-Nilsen.
Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary.
SODA 2020: 2542-2561.
M. P. Gutenberg and C. Wulff-Nilsen.
Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler.
SODA 2020: 2522-2541.
M. P. Gutenberg and C. Wulff-Nilsen.
Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary.
CoRR abs/2001.10821, 2020.
M. P. Gutenberg and C. Wulff-Nilsen.
Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds.
CoRR abs/2001.10801, 2020.
M. P. Gutenberg, C. Wulff-Nilsen.
Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler.
CoRR abs/2001.10809, 2020.
S. Alstrup, S. Dahlgaard, A. Filtser, M. Stöckel, and C. Wulff-Nilsen.
Constructing Light Spanners Deterministically in Near-Linear Time.
ESA 2019: 4:1-4:15.
A. Bernstein, M. Probst, and C. Wulff-Nilsen.
Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time.
STOC 2019: 365-376.
A. Bernstein, M. Probst, and C. Wulff-Nilsen.
Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time.
CoRR abs/1901.03615 (2019).
G. Borradaile, H. V. Le, and C. Wulff-Nilsen.
Greedy spanners are optimal in doubling metrics.
SODA 2019: 2371-2379.
S. Chechik and C. Wulff-Nilsen.
Near-Optimal Light Spanners.
ACM Trans. Algorithms 14(3): 33:1-33:15 (2018).
P. Gawrychowski, S. Mozes, O. Weimann, and C. Wulff-Nilsen.
Better Tradeoffs for Exact Distance Oracle in Planar Graphs.
SODA 2018: 515-529.
D. Nanongkai, T. Saranurak, and C. Wulff-Nilsen.
Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time.
FOCS 2017:950-961.
V. V. Cohen-Addad, S. Dahlgaard, and C. Wulff-Nilsen.
Fast and Compact Exact Distance Oracle for Planar Graphs.
FOCS 2017:962-973.
G. Borradaile, H. V. Le, and C. Wulff-Nilsen.
Minor-free graphs have light spanners.
FOCS 2017:767-778.
C. Wulff-Nilsen.
Fully-Dynamic Minimum Spanning Forest with Improved Worst-Case Update Time.
STOC 2017: 1130-1143.
M. Abrahamsen, J. Holm, E. Rotenberg, and C. Wulff-Nilsen.
Best Laid Plans of Lions and Men.
SoCG 2017: 6:1 - 6:16.
V. Cohen-Addad, S. Dahlgaard, and C. Wulff-Nilsen.
Fast and Compact Exact Distance Oracle for Planar Graphs.
arXiv:1702.03259 [cs.DS], February 2017.
C. Wulff-Nilsen.
Fully-Dynamic Minimum Spanning Forest with Improved Worst-Case Update Time.
arXiv:1611.02864v2 [cs.DS], November 2016.
G. Borradaile, D. Eppstein, C. Wulff-Nilsen, and A. Nayyeri.
All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs.
SoCG 2016: 22:1-22:16.
C. Petersen, N. Rotbart, J. Grue-Simonsen, and C. Wulff-Nilsen.
Near Optimal Adjacency Labeling Schemes for Power-Law Graphs.
ICALP 2016: 133:1-133:15.
C. Wulff-Nilsen.
Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff.
SODA 2016: 351-362.
S. Chechik and C. Wulff-Nilsen.
Near-Optimal Light Spanners.
SODA 2016: 883-892 (best paper award).
C. Wulff-Nilsen.
Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff.
arXiv:1601.00839 [cs.DS], January 2016.
M. Elkin, O. Neimann, and C. Wulff-Nilsen.
Space-efficient path-reporting approximate distance oracles.
Theor. Comput. Sci. 651: 1-10, 2016.
J. Holm, E. Rotenberg, and C. Wulff-Nilsen.
Faster Fully-Dynamic Minimum Spanning Forest.
ESA 2015, LNCS 9294, pp. 742-753, 2015.
G. Borradaile, P. Sankowski, and C. Wulff-Nilsen
Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time.
ACM Transactions on Algorithms 11(3): 16, 2015.
C. Wulff-Nilsen
Approximate Distance Oracles with Improved Query Time.
Encyclopedia of Algorithms, 2015.
G. Borradaile, D. Eppstein, A. Nayyeri, and C. Wulff-Nilsen
All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs.
arXiv:1411.7055 [cs.CG], November 2014.
M. Elkin, O. Neiman, and C. Wulff-Nilsen
Space-Efficient Path-Reporting Approximate Distance Oracles.
arXiv:1410.0768 [cs.DS], October 2014.
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.
C. Wulff-Nilsen
Constant Time Distance Queries in Planar Unweighted Graphs with Subquadratic Preprocessing Time.
Computational Geometry, Volume 46, Issue 7, October 2013, p. 831–838, special issue on the 25th European Workshop on Computational Geometry.
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, A. Grüne, R. Klein, E. Langetepe, D. T. Lee, T. Lin, S. Poon, and T. Yu
Computing the Stretch factor and Maximum Detour of Paths, Trees, and cycles in the normed Space.
Int. J. Comput. Geometry Appl. 22(1):45-60, 2012.
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.
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.