wiki_research

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

reachability_all_pairs (385B)

      1 # All pairs reachability
      2 
      3 - On [undirected_graphs]:
      4   - Easy, it suffices to compute [connected_components]
      5 - On [directed_graphs]:
      6   - amounts to [transitive_closure]
      7   - can be done in time O(mn)
      8   - the result may have [quadratic] size, even if the [graph] is [sparse_graph]
      9   - equivalent to [boolean_matrix_multiplication]
     10 
     11 Up: [reachability]
     12 
     13 See also: [all_pairs_shortest_path]