Research

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
beyond-planarity

Teaching

Courses I’m teaching or have taught at the University of Vienna can be found here.

Student theses:

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
Dynamic Subgraph Counting
Dynamic Graph Algorithms
“Intelligent” Graph Algorithms
Online Min-Max Paging
…

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):

Julian Unterweger. Covering Rectilinear Polygons with Few and Small Axis-Aligned Rectangles. 2023.
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.

Software Projects

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.

C++ implementation of our algorithm to speedup reachability queries in static graphs. See also the website of the corresponding paper.

image Gravisto - A Graph Drawing Toolkit

Actually a toolkit for drawing graphs, but contains also a number of other algorithms. Written in Java.