Publications (13)
Expander Hierarchies for Normalized Cuts on Graphs
Kathrin Hanauer, Monika Henzinger, Robin Münk +2
Expander decompositions of graphs have significantly advanced the understanding of many classical graph problems and led to numerous fundamental theoretical results. However, their…
Faster Fully Dynamic Transitive Closure in Practice
Kathrin Hanauer, Monika Henzinger, Christian Schulz
The fully dynamic transitive closure problem asks to maintain reachability information in a directed graph between arbitrary pairs of vertices, while the graph undergoes a sequence…
O'Reach: Even Faster Reachability in Large Graphs
Kathrin Hanauer, Christian Schulz, 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…
On -Matching and Fully-Dynamic Maximum -Edge Coloring
Antoine El-Hayek, Kathrin Hanauer, Monika Henzinger
Given a graph that is modified by a sequence of edge insertions and deletions, we study the Maximum -Edge Coloring problem Having access to colors, how can we color as m…
Fast and Heavy Disjoint Weighted Matchings for Demand-Aware Datacenter Topologies
Kathrin Hanauer, Monika Henzinger, Stefan Schmid +1
Reconfigurable optical topologies promise to improve the performance in datacenters by dynamically optimizing the physical network in a demand-aware manner. State-of-the-art optica…
A Note on IC-Planar Graphs
Christian Bachmaier, Franz J. Brandenburg, Kathrin Hanauer
A graph is IC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share no common end vertex. IC-planarity speci…
Fully Dynamic Single-Source Reachability in Practice: An Experimental Study
Kathrin Hanauer, Monika Henzinger, Christian Schulz
Given a directed graph and a source vertex, the fully dynamic single-source reachability problem is to maintain the set of vertices that are reachable from the given vertex, subjec…
Improved Exact and Heuristic Algorithms for Maximum Weight Clique
Roman Erhardt, Kathrin Hanauer, Nils Kriege +2
We propose improved exact and heuristic algorithms for solving the maximum weight clique problem, a well-known problem in graph theory with many applications. Our algorithms interl…
Recent Advances in Fully Dynamic Graph Algorithms
Kathrin Hanauer, Monika Henzinger, 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…
Fully Dynamic Four-Vertex Subgraph Counting
Kathrin Hanauer, Monika Henzinger, Qi Cheng Hua
This paper presents a comprehensive study of algorithms for maintaining the number of all connected four-vertex subgraphs in a dynamic graph. Specifically, our algorithms maintain…
Dynamic Demand-Aware Link Scheduling for Reconfigurable Datacenters
Kathrin Hanauer, Monika Henzinger, Lara Ost +1
Emerging reconfigurable datacenters allow to dynamically adjust the network topology in a demand-aware manner. These datacenters rely on optical switches which can be reconfigured…
NIC-Planar Graphs
Christian Bachmaier, Franz J. Brandenburg, Kathrin Hanauer +2
A graph is NIC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share at most one common end vertex. NIC-plan…
Covering Rectilinear Polygons with Area-Weighted Rectangles
Kathrin Hanauer, Martin P. Seybold, Julian Unterweger
Representing a polygon using a set of simple shapes has numerous applications in different use-case scenarios. We consider the problem of covering the interior of a rectilinear pol…