1 citations · 1 across the 6 of their papers we have counts for
10 papers · 1 filter
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 …
Revisiting a Successful Reduction Rule for Dominating Set
Lukas Geis, Alexander Leonhardt, Johannes Meintrup +3
Given a graph with vertices and edges, the DominatingSet problem asks for a set of minimal cardinality such that every vertex either is in …
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…
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…
Open Problems in (Hyper)Graph Decomposition
Deepak Ajwani, Rob H. Bisseling, Katrin Casel +26
Large networks are useful in a wide range of applications. Sometimes problem instances are composed of billions of entities. Decomposing and analyzing these structures helps us gai…
Kernelizing Problems on Planar Graphs in Sublinear Space and Polynomial Time
Arindam Biswas, Johannes Meintrup
In this paper, we devise a scheme for kernelizing, in sublinear space and polynomial time, various problems on planar graphs. The scheme exploits planarity to ensure that the resul…
Succinct Planar Encoding with Minor Operations
Frank Kammer, Johannes Meintrup
Let be an unlabeled planar and simple -vertex graph. Unlabeled graphs are graphs where the label-information is either not given or lost during the construction of data-stru…
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 -vertex planar graphs , called cloud partition, which partitions the vertices into disjoint sets …
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…
Space-Efficient Vertex Separators for Treewidth
Frank Kammer, Johannes Meintrup, Andrej Sajenko
For -vertex graphs with treewidth and an arbitrary , we present a word-RAM algorithm to compute vertex separators using only bits of working memor…