Andrej Sajenko

activity

20182020

most citedLinear-Time In-Place DFS and BFS on the Word RAM

2 citations · 2 across the 5 of their papers we have counts for

collaborators

Showing 2019Show all

2 papers · 1 filter

cs.CC2019

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…

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…