Skip to content

Instantly share code, notes, and snippets.

@wolfram77

wolfram77/notes-a-parallel-algorithm-template-for-updating-singlesource-shortest-paths-in-largescale-dynamic-networks.md

Last active September 26, 2021 02:25
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save wolfram77/dc6c7bf55a2de50098b5fdc03be0d759 to your computer and use it in GitHub Desktop.
Save wolfram77/dc6c7bf55a2de50098b5fdc03be0d759 to your computer and use it in GitHub Desktop.
Download ZIP
A Parallel Algorithm Template for Updating Single-Source Shortest Paths in Large-Scale Dynamic Networks : NOTES
Raw
notes-a-parallel-algorithm-template-for-updating-singlesource-shortest-paths-in-largescale-dynamic-networks.md

Highlighted notes on:
A Parallel Algorithm Template for Updating Single-Source Shortest Paths in Large-Scale Dynamic Networks.
While doing research work with Prof. Dip Sankar Banerjee, Prof, Kishore Kothapalli.

For SSSP the researchers give an update algorithm for handling edge insertion and deletion. They implement for in OpenMP & CUDA and compare with Galois & Gunrock resp. For each vertex there are additional "affected" flags. In a later step "affected" flag is used iteratively update distances. To avoid loops disconnected vertices are set to INF. Edge deletions are slower (needs tree repair).

They have shown graphs for 50M, 100M changes, but i couldnt find what batch size they use. Is it 50/100M? Later they did mention experiment with batch size 15, 30, 50? Is it 50 changes of 50M changes?

Display the source blob
Display the rendered blob
Raw
notes-a-parallel-algorithm-template-for-updating-singlesource-shortest-paths-in-largescale-dynamic-networks.pdf
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment