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
314489
de