Graph Theory37 sections · 1633 units
Open in Course

Low-Link Value

(Earliest reachable ancestor)

The low-link value low[v] is the smallest discovery time reachable from the subtree rooted at vv. In other words: low[v] is the earliest vertex you can reach from vv using tree edges going down and at most one back edge going up. If low[v] = disc[v], then no back edges escape the subtree of vv.

This means vv is isolated unless its parent edge is the only connection. This condition identifies bridges and articulation points.