We reconsider basic algorithmic graph problems in a setting where an n-vertex input graph
is read-only and the computation must take place in a working memory of O (n) bits or little …

Dynamic programming on path and tree decompositions of graphs is a technique that is
ubiquitous in the field of parameterized and exponential-time algorithms. However, one of its …

We give an almost quadratic n 2− o (1) lower bound on the space consumption of any o (√
log n)-pass streaming algorithm solving the (directed) st reachability problem. This means …

The directed graph reachability problem takes as input an n-vertex directed graph G=(V, E),
and two distinguished vertices v 0, and vertex v*. The problem is to determine whether there …

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 show that the reach ability problem over\em directed planar graphs can be solved
simultaneously in polynomial time and approximately O(n) space. In contrast, the best space …

We obtain the following new simultaneous time-space upper bounds for the directed
reachability problem.(1) A polynomial-time, O (n^{2/3}* g^{1/3})-space algorithm for directed …

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 …

Influence Maximization is an important problem in data science. Current solutions with
theoretical guarantees are space-inefficient and have limited parallelism, limiting their …

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 …