wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

simple_path_problem (284B)

      1 # Simple path problem
      2 
      3 [Computational_problem] of deciding if there is a [simple_path] in a [graph] from a vertex s to a vertex t
      4 
      5 Obviously [PTIME] by computing a [shortest_path]
      6 
      7 - [simple_path_rpq_problem]
      8 - [simple_path_parity_problem]
      9 
     10 Up: [computational_problem], [simple_path]