PhD defence by Jacob Holm

Title

Efficient Graph algorithms and Data Structures

Abstract

The graph is one of the most important abstractions used in computer science. This thesis gives substantial improvements to the state of the art regarding 4 different problems on static or dynamic graphs, namely: Static reachability in planar graphs, Online bipartite matching with recourse, Deterministic fully-dynamic 2-edge connectivity and bridge-finding, and Strong trail orientations of graphs.

Assessment Committee:

Chairman: Associate Professor Thomas Dueholm Hansen, Department of Computer Science, University of Copenhagen
Professor Valerie King, Department of Computer Science, University of Victoria, Canada
Professor Uri Zwick, Department of Computer Science, Tel-Aviv University, Israel

Academic supervisor & Co-Supervisor:

Professor Mikkel Thorup, Department of Computer Science, University of Copenhagen​
Co-Supervisor Professor Stephen Alstrup, Department of Computer Science, University of Copenhagen

For an electronic copy of the thesis, please contact phdadmin@di.ku.dk