st-non-connectivity
From Wikipedia, the free encyclopedia
st-non-connectivity refers to a problem in computer science and computational complexity theory, a decision problem asking if two vertices s and t in a directed graph are not connected by a path.
The algorithm is in the complexity class co-NL, and hence in the class NL, by the Immerman-Szelepcsényi Theorem.
