7 papers
On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering
Aleksander Figiel, Anne-Sophie Himmel, André Nichterlein +1
Editing a graph into a disjoint union of clusters is a standard optimization task in graph-based data clustering. Here, complementing classic work where the clusters shall be cliqu…
Multistage Graph Problems on a Global Budget
Klaus Heeger, Anne-Sophie Himmel, Frank Kammer +3
Time-evolving or temporal graphs gain more and more popularity when studying the behavior of complex networks. In this context, the multistage view on computational problems is amo…
The Computational Complexity of Finding Temporal Paths under Waiting Time Constraints
Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter +1
Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, grap…
Efficient Computation of Optimal Temporal Walks under Waiting-Time Constraints
Anne-Sophie Himmel, Matthias Bentert, André Nichterlein +1
Node connectivity plays a central role in temporal network analysis. We provide a comprehensive study of various concepts of walks in temporal graphs, that is, graphs with fixed ve…
Listing All Maximal -Plexes in Temporal Graphs
Matthias Bentert, Anne-Sophie Himmel, Hendrik Molter +3
Many real-world networks evolve over time, that is, new contacts appear and old contacts may disappear. They can be modeled as temporal graphs where interactions between vertices (…
Computational Complexity Aspects of Point Visibility Graphs
Anne-Sophie Himmel, Clemens Hoffmann, Pascal Kunz +2
A point visibility graph is a graph induced by a set of points in the plane where the vertices of the graph represent the points in the point set and two vertices are adjacent if a…