Andrej Sajenko

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2019

Space-Efficient Vertex Separators for Treewidth

Frank Kammer, Johannes Meintrup, Andrej Sajenko

For $n$ -vertex graphs with treewidth $k = O (n^{1/2 - ε})$ and an arbitrary $ε > 0$ , we present a word-RAM algorithm to compute vertex separators using only $O (n)$ bits of working memor…

cs.DS2018

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…

cs.DS2018

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…