3 papers
cs.DS2025
Space-Efficient Depth-First Search via Augmented Succinct Graph Encodings
Michael Elberfeld, Frank Kammer, Johannes Meintrup
We call a graph separable if a balanced separator can be computed for of size with . 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 -bit sequence of 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…