mohit created GIRAPH-1254:
-----------------------------
Summary: A linear round complexity algorithm for unweighted, exact
all pairs shortest path (APSP)
Key: GIRAPH-1254
URL: https://issues.apache.org/jira/browse/GIRAPH-1254
Project: Giraph
Issue Type: New Feature
Components: examples
Affects Versions: 1.3.0
Reporter: mohit
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
# weighted vs unweighted
# randomized vs deterministic
# exact vs approximation
# permission for message passing, and message size
## between only adjacent vertices
## 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.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
