[GIRAPH-1254] A linear round complexity algorithm for unweighted, exact all pairs shortest path (APSP)

• Type: New Feature
• Status: Open
• Priority: Minor
• Resolution: Unresolved
• Affects Version/s: 1.3.0
• Component/s: examples
• Assignee: Unassigned
• Reporter: mohit
• Created: 28/Mar/22 19:48
• Updated: 29/Mar/22 15:57

Description

In the theory community (mainly targeting PODC, SODA, FOCS, and STOC), several graph algorithms for APSP have been developed in the abstract model of vertex-centric computation. These distinguished themselves upon

1. weighted vs unweighted
2. randomized vs deterministic
3. exact vs approximation
4. permission for message passing, and message size
   1. between only adjacent vertices
   2. between any two vertices in the graph

This Jira is to implement a simple linear-time algorithm for APSP (discussed on the dev list). An algorithm for a fundamental problem like APSP has several practical use cases, for example in developing large scale recommender systems. This implementation would also lead the way forward for some recent results claiming poly log round complexity for various graph algorithms in the aforementioned graph model.