5 papers
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…