  The width measure treedepth, also known as vertex ranking, centered coloring
and elimination tree height, is a well-established notion which has recently
seen a resurgence of interest. Since graphs of bounded treedepth are more
restricted than graphs of bounded tree- or pathwidth, we are interested in the
algorithmic utility of this additional structure.
  On the negative side, we show that every dynamic programming algorithm on
treedepth decompositions of depth~$t$ cannot solve Dominating Set with
$O((3-\epsilon)^t \cdot \log n)$ space for any $\epsilon > 0$. This result
implies the same space lower bound for dynamic programming algorithms on tree
and path decompositions. We supplement this result by showing a space lower
bound of $O((3-\epsilon)^t \cdot \log n)$ for 3-Coloring and $O((2-\epsilon)^t
\cdot \log n)$ for Vertex Cover. This formalizes the common intuition that
dynamic programming algorithms on graph decompositions necessarily consume a
lot of space and complements known results of the time-complexity of problems
restricted to low-treewidth classes.
  We then show that treedepth lends itself to the design of branching
algorithms. This class of algorithms has in general distinct advantages over
dynamic programming algorithms: a) They use less space than algorithms based on
dynamic programming, b) they are easy to parallelize and c) they provide
possible solutions before terminating.
  Specifically, we design for Dominating Set a pure branching algorithm that
runs in time $t^{O(t^2)}\cdot n$ and uses space $O(t^3 \log t + t \log n)$ and
a hybrid of branching and dynamic programming that achieves a running time of
$O(3^t \log t \cdot n)$ while using $O(2^t t \log t + t \log n)$ space.
Algorithms for 3-Coloring and Vertex Cover with space complexity $O(t \cdot
\log n)$ and time complexity $O(3^t \cdot n)$ and $O(2^t\cdot n)$,
respectively, are included for completeness.
