= Depth-first search parenthesis property
{title2=$d(u)<d(v)<f(v)<f(u)$}
= DFS parenthesis property
{c}
{synonym}
The discovery-to-finishing intervals of distinct <vertices> in a <depth-first search> are either disjoint or strictly nested. A recursive call completes before its caller returns; separate completed branches have disjoint intervals. Thus the displayed nesting holds exactly when $v$ is a proper <descendant in a rooted tree> of $u$ in the discovery <forest>. A <directed path> alone does not imply this nesting, because it can leave the current branch through an already discovered ancestor.
Back to article page
