wiki_research

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

apsp_reduces_to_distance_product (314B)

      1 # APSP reduces to distance product
      2 
      3 [fine_grained_reduction] from [all_pairs_shortest_path] to computing [distance_product]
      4 
      5 Take [adjacency_matrix] of a [graph], do [fast_exponentiation] to get the weight of
      6 the [shortest_path] of <= n edges
      7 
      8 
      9 
     10 Up: [reduction] from [all_pair_shortest_path] to [distance_product]