Kathrin Hanauer

Kathrin Hanauer

Auto-generated profile, based on publicly available information

Kathrin Hanauer

Faculty of Computer Science, University of Vienna, Vienna, Austria

Research Focus & Metrics

Academic Career Length

5Years (2022-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
13 December 2022 in ACM Journal of Experimental Algorithmics
Verified
Journal Article
Open access
KHKathrin Hanauer
Kathrin Hanauer
MHMonika Henzinger
Monika Henzinger
CSChristian Schulz
Christian Schulz
In recent years, significant advances have been made in the design and analysis of fully dynamic algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. Here, we present a quick reference guide to recent engineering and theory results in the area of fully dynamic graph algorithms.

21 October 2022 in ACM Journal of Experimental Algorithmics
Verified
Journal Article
Open access
KHKathrin Hanauer
Kathrin Hanauer
CSChristian Schulz
Christian Schulz
JTJonathan Trummer
Jonathan Trummer
One of the most fundamental problems in computer science is the reachability problem : Given a directed graph and two vertices s and t , can s reach t via a path? We revisit existing techniques and combine them with new approaches to support a large portion of reachability queries in constant time using a linear-sized reachability index . Our new algorithm O’Reach can be easily combined with previously developed solutions for the problem or run standalone. In a detailed experimental study, we compare a variety of algorithms with respect to their index-building and query times as well as their memory footprint on a diverse set of instances. Our experiments indicate that the query performance often depends strongly not only on the type of graph but also on the result, i.e., reachable or unreachable . Furthermore, we show that previous algorithms are significantly sped up when combined with our new approach in almost all scenarios. Surprisingly, due to cache effects, a higher investment in space doesn’t necessarily pay off: Reachability queries can often be answered even faster than single memory accesses in a precomputed full reachability matrix.

24 August 2024
Verified
Conference Paper
Open access
KHKathrin Hanauer
Kathrin Hanauer
MHMonika Henzinger
Monika Henzinger
RMRobin Münk
Robin Münk
HRHarald Räcke
Harald Räcke
MVMaximilian Vötsch
Maximilian Vötsch
Expander decompositions of graphs have significantly advanced the understanding of many classical graph problems and led to numerous fundamental theoretical results. However, their adoption in practice has been hindered due to their inherent intricacies and large hidden factors in their asymptotic running times. Here, we introduce the first practically efficient algorithm for computing expander decompositions and their hierarchies and demonstrate its effectiveness and utility by incorporating it as the core component in a novel solver for the normalized cut graph clustering objective. Our extensive experiments on a variety of large graphs show that our expander-based algorithm outperforms state-of-the-art solvers for normalized cut with respect to solution quality by a large margin on a variety of graph classes such as citation, e-mail, and social networks or web graphs while remaining competitive in running time.

7 December 2023
Verified
Book Chapter
Open access
PDF file
KHKathrin Hanauer
Kathrin Hanauer
TNTereza Novotná
Tereza Novotná
MPMatteo Pascucci
Matteo Pascucci
We design a framework for assisted normative reasoning based on Aristotelian diagrams and algorithmic graph theory which can be employed to address heterogeneous tasks of deductive reasoning. Here we focus on two problems of normative determination: we show that the algorithms used to address these problems are computationally efficient and their operations are traceable by humans. Finally, we discuss an application of our framework to a scenario regulated by the GDPR.