54 citations · 62 across the 10 of their papers we have counts for
15 papers
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 …
Space-Efficient Graph Kernelizations
Frank Kammer, Andrej Sajenko
Let be the size of a parameterized problem and the parameter. We present kernels for Feedback Vertex Set, Path Contraction and Cluster Editing/Deletion whose sizes are all…
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…
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…
Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays
Frank Kammer, Andrej Sajenko
Many succinct data structures on the word RAM require precomputed tables to start operating. Usually, the tables can be constructed in sublinear time. In this time, most of a data…
Linear-Time In-Place DFS and BFS on the Word RAM
Frank Kammer, Andrej Sajenko
We present an in-place depth first search (DFS) and an in-place breadth first search (BFS) that runs on a word RAM in linear time such that, if the adjacency arrays of the input gr…
On-the-Fly Array Initialization in Less Space
Torben Hagerup, Frank Kammer
We show that for all given with , an array of entries of bits each can be represented on a word RAM with a word length of bits in at most…
Space-Efficient Hidden Surface Removal
Frank Kammer, Maarten Löffler, Rodrigo I. Silveira
We propose a space-efficient algorithm for hidden surface removal that combines one of the fastest previous algorithms for that problem with techniques based on bit manipulation. S…
Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs
Frank Kammer, Dieter Kratsch, Moritz Laudahn
We present space-efficient algorithms for computing cut vertices in a given graph with vertices and edges in linear time using bits. With the…
Succinct Choice Dictionaries
Torben Hagerup, Frank Kammer
The choice dictionary is introduced as a data structure that can be initialized with a parameter and subsequently maintains an initially empty subse…
Space-Efficient Plane-Sweep Algorithms
Amr Elmasry, Frank Kammer
We introduce space-efficient plane-sweep algorithms for basic planar geometric problems. It is assumed that the input is in a read-only array of items and that the available wo…
On Temporal Graph Exploration
Thomas Erlebach, Michael Hoffmann, Frank Kammer
A temporal graph is a graph in which the edge set can change from one time step to the next. The temporal graph exploration problem TEXP is the problem of computing a foremost expl…
Approximate Tree Decompositions of Planar Graphs in Linear Time
Frank Kammer, Torsten Tholey
Many algorithms have been developed for NP-hard problems on graphs with small treewidth . For example, all problems that are expressable in linear extended monadic second order…
Removing Local Extrema from Imprecise Terrains
Chris Gray, Frank Kammer, Maarten Loffler +1
In this paper we consider imprecise terrains, that is, triangulated terrains with a vertical error interval in the vertices. In particular, we study the problem of removing as many…