Johannes Meintrup

activity

20242026

collaborators

6 papers

cs.DS2026

Breadth-First Search in Succinct Planar Graphs

Johannes Meintrup

We present a succinct encoding of planar graphs that supports executing a breadth-first search directly on the encoding. The succinct encoding can be constructed in expected $O (n)$ …

cs.DS2025

Revisiting a Successful Reduction Rule for Dominating Set

Lukas Geis, Alexander Leonhardt, Johannes Meintrup +3

Given a graph $G = (V, E)$ with $n$ vertices and $m$ edges, the DominatingSet problem asks for a set $D \subseteq V$ of minimal cardinality such that every vertex either is in $D$ …

cs.DS2025

Space-Efficient Depth-First Search via Augmented Succinct Graph Encodings

Michael Elberfeld, Frank Kammer, Johannes Meintrup

We call a graph $G$ separable if a balanced separator can be computed for $G$ of size $O (n^{c})$ with $c < 1$ . Many real-world graphs are separable such as graphs of bounded genus, gra…

cs.DS2024

Sorting and Ranking of Self-Delimiting Numbers with Applications to Outerplanar Graph Isomorphism

Frank Kammer, Johannes Meintrup, Andrej Sajenko

Assume that an $N$ -bit sequence $S$ of $k$ numbers encoded as Elias gamma codes is given as input. We present space-efficient algorithms for sorting, dense ranking and competitive…

cs.DS2024

Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous

Konstantinos Dogeas, Thomas Erlebach, Frank Kammer +2

Temporal graphs are graphs where the edge set can change in each time step, and the vertex set stays the same. Exploration of temporal graphs whose snapshot in each time step is a…

cs.DS2024

Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings

Nina Hammer, Frank Kammer, Johannes Meintrup

We present a novel space-efficient graph coarsening technique for $n$ -vertex planar graphs $G$ , called cloud partition, which partitions the vertices $V (G)$ into disjoint sets $C$ …