5 papers · 1 filter
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 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…