St-non-connectivity
From Wikipedia, the free encyclopedia
- The correct title of this article is st-non-connectivity. The initial letter is shown capitalized due to technical restrictions.
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.
