A universal bound on the space complexity of Directed Acyclic Graph computations

Gianfranco Bilardi, Lorenzo De Stefani

It is shown that $S(G)=O\left(m/{\log }_{2}m+d\right)$ pebbles are sufficient to pebble any DAG $G=(V,E)$, with $m$ edges and maximum in-degree $d$. It was previously known that $S…