wiki_research

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

apsp_reduces_to_distance_product (275B)

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