st-connectivity
Sign in to saveAlso known as STCON, graph accessibility problem, GAP
thumb|300px|There is a path (graph theory)|path directed from "s" to "t" in the first graph, but not in the second.
~3 min read
Article
2 sectionsContents
- Complexity
- References
thumb|300px|There is a path (graph theory)|path directed from "s" to "t" in the first graph, but not in the second.
In computer science, st-connectivity or STCON is a decision problem asking, for vertices s and t in a directed graph, if t is reachable from s.
Connections
graph connectivity measure
Entity
computer science
Entity
International Standard Book Number
Entity
graph
Entity
depth-first search
Entity
breadth-first search
Entity
directed graph
Entity
decision problem
Entity
time complexity
Entity
P
Entity
complexity class
Entity
path
Entity
non-deterministic Turing machine
Entity
strongly connected component
Entity
NL
Entity
bridge
Entity
L
Entity
Grace Murray Hopper Award
Entity
Savitch's theorem
Entity
Neil Immerman
Entity