St-connectivity

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.

Formally, the decision problem is given by

PATH = {⟨D, s, t⟩ | D is a directed graph with a path from vertex s to t}.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.