incubator-hama-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Andreas Gebhardt (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (HAMA-359) Development of Shortest Path Finding Algorithm
Date Sun, 24 Apr 2011 14:57:05 GMT

    [ https://issues.apache.org/jira/browse/HAMA-359?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13024630#comment-13024630
] 

Andreas Gebhardt commented on HAMA-359:
---------------------------------------

Very nice!

Beside Metis/Parmetis there exists another partitioning tool named Scotch -- http://www.labri.fr/perso/pelegrin/scotch/
-- this is amongst others used in SHARC algorithm (e.g. i11www.iti.uni-karlsruhe.de/extra/publications/d-tdsr-09.pdf).
This is a algorithm for shortest path (via Dijkstra), the incredible speed is achieved by
massive preprocessing. The research of very fast dijkstra implementation seemed to begun for
the 9th DIMACS implementation challenge (http://www.dis.uniroma1.it/~challenge9/). Hopefully
the combination of both can be very interesting.

On there web-site of DIMACS the 10th challenge is for graph partitoning http://www.cc.gatech.edu/dimacs10/index.shtml
...

While searching for the address of SCOTCH i found this link https://gforge.inria.fr/forum/message.php?msg_id=105188&group_id=248
- there are some additional links at the end of the thread.

Andreas

> Development of Shortest Path Finding Algorithm
> ----------------------------------------------
>
>                 Key: HAMA-359
>                 URL: https://issues.apache.org/jira/browse/HAMA-359
>             Project: Hama
>          Issue Type: New Feature
>          Components: examples
>    Affects Versions: 0.2.0
>            Reporter: Edward J. Yoon
>            Assignee: Edward J. Yoon
>              Labels: gsoc, gsoc2011, mentor
>             Fix For: 0.3.0
>
>   Original Estimate: 2016h
>  Remaining Estimate: 2016h
>
> The goal of this project is development of parallel algorithm for finding a Shortest
Path using Hama BSP.

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

Mime
View raw message