Research on space efficient graph algorithms, particularly for st-connectivity, has a long
history including the celebrated polynomial time, O (lg n) bits 1 algorithm in undirected …

Recent work by Elmasry et al.(STACS 2015) and Asano et al.(ISAAC 2014), reconsidered
classical fundamental graph algorithms focusing on improving the space complexity …

We present space-efficient algorithms for computing cut vertices in a given graph with n
vertices and m edges in linear time using O (n+\min {m, n\log\log n\}) O (n+ min m, n log log …

We present a novel space-efficient graph coarsening technique for $ n $-vertex planar
graphs $ G $, called cloud partition, which partitions the vertices $ V (G) $ into disjoint sets …

The problem of space-efficient depth-first search (DFS) is reconsidered. A particularly simple
and fast algorithm is presented that, on a directed or undirected input graph G=(V, E) G=(V …

The lexicographic depth-first search (Lex-DFS) is one of the first basic graph problems
studied in the context of space-efficient algorithms. It is shown independently by Asano et …

We describe space-efficient algorithms for two problems on undirected multigraphs: Euler
partition (partitioning the edges into a minimum number of trails); and bipartite edge coloring …

Read-only memory (ROM) model is a classical model of computation to study time-space
tradeoffs of algorithms. A classical result on the ROM model is that any algorithm to sort n …

The choice dictionary is introduced as a data structure that can be initialized with a
parameter $ n\in\mathbb {N}=\{1, 2,\ldots\} $ and subsequently maintains an initially empty …

Graph-walking automata (GWA) are finite-state devices that traverse graphs given as an
input by following their edges; they have been studied both as a theoretical notion and as a …