Dr. Kathrin Hanauer, B.Sc. M.Sc.
Währinger Straße 29, 1090 Wien
Consultation: any time in general, but better send a short e-mail beforehand
I am interested in the design, analysis, and experimental evaluation of fast algorithms and especially in Algorithm Engineering. Algorithm Engineering connects algorithm theory with practice and focuses on the performance of algorithms in real-life scenarios. Besides what is typically considered a “fast” algorithm (one that runs in polynomial time and with a small exponent), my research is also concerned with so-called “intractable” problems with exponential worst-case running time.
Much of my recent work is devoted to dynamic algorithms: The typical, “static” setting is as follows: an algorithm receives some input, does some computations, and returns a solution. If the data changes, it has to recompute everything from scratch. By contrast, a dynamic algorithm can handle the changes to the data itself and only needs to update its solution – which can save a lot of time, especially on huge data sets!
I particularly enjoy working with graphs and graph algorithms. Graphs are a powerful tool for modelling all sorts of relationships and interactions. Depending on the scenario, they may also exhibit very different structure and characteristics, and being aware of this unlocks potential for further improvements of the algorithms that operate on them.
Current and previous research areas (selection):
- network analysis, motif search, and subgraph counting
- algorithms for data center technologies
- reachability problems on directed graphs
- ranking problems, in particular the NP-hard Feedback Arc Set problem
Courses I’m teaching or have taught at the University of Vienna can be found here.
We have many open topics suitable for student thesis both on Bachelor’s and Master’s level. To do your Bachelor’s or Master’s thesis with us, you should have
- a profound understanding of algorithms and data structures,
- joy working and experimenting with them,
- excellent programming skills (usually in C++),
- a certain amount of perseverance ;-) and the ability to think for yourself!
Possible topics and subject areas (updated/extended regularly):
- Patterns in Dynamic and/or Temporal Graphs
- Dynamic Orbit Partition
- Dynamic Algorithms with Non-Trivial Update Operations
Kernelization for Clique Solvers
- Dynamic Subgraph Counting
- Dynamic Graph Algorithms
- “Intelligent” Graph Algorithms
If you would be interested in a topic or area that is not listed here, feel free to suggest your own topic!
Recently completed topics (@UniVie):
- Leonhard Paul Sidl. Algorithm Engineering for Fully Dynamic Subgraph Counting. 2022.
- Jonathan Trummer. Engineering Maximum Common Subgraph Algorithms for Large Graphs. 2021.
- Qi Cheng Hua. Fully Dynamic Detection of Constant-Size Subgraphs. 2021.
- Tabea Reichmann. Update Your Network - Loop Free. 2021.
- Alwin Stockinger. Dynamic All-Pairs Reachability on Partitioned Graphs. 2019.
- Rosa Zimmermann. A Heuristic Algorithm for Graph-Based Surface Segmentation in Volumetric Images. 2018.
A modular algorithms library with support for dynamic graphs, written in C++.
C++ implementation of a number of different algorithms that solve the k-disjoint matchings problem. See the corresponding paper for details on the problem and our algorithms.
Actually a toolkit for drawing graphs, but contains also a number of other algorithms. Written in Java.