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?
