St-connectivity
The reachability problem in graph ( also STCON, GAP, PATH or REACH ) deals with the question of whether there is a path from a node to a node in a graph. Does such a way, so is accessible from from. Otherwise is not reachable from from.
The acronym is short for STCON. s- t- connectivity, GAP for engl. Graph Accessibility Problem and REACH for engl. Reachability. The analogous problem for undirected graphs is called USTCON.
The reachability problem is NL -complete problem. It can be solved for example using the breadth-first search or depth-first search.
Statements and phrases
- In undirected graphs each node of any other node is exactly achievable if the graph is connected.
- In directed graphs, this is exactly the case when the graph is strongly connected.
- The problem STCON is NL -complete.
- The problem is in STCON ( set of Savitch )
- The problem lies in the complexity class USTCON L.
Idea of proof for STCON is NL -complete
It is to show that any problem can be reduced in NL on STCON and STCON is in NL.
Swell
- Christos H. Papadimitriou Computational Complexity. Addison Wesley, ISBN 978-0201530827
- Problem (graph theory )
- Complexity Theory