2 citations · 2 across the 5 of their papers we have counts for
6 papers
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…
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…
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…