Efficient Parallel Algorithm for Shortest Path Updates in Dynamic Networks at Scale

Student: Arindam Khanda (Missouri University of Science and Technology)
Supervisor: Sajal K. Das (Missouri University of Science and Technology)

Abstract: The application of graphs (networks) are versatile, and they are applied to various fields, including but not limited to social network analysis, transportation logistics, biological and genetic interaction study, IP traffic routing, and resource allocation in IoT networks. All these domains deal with a massive amount of data and require large-scale graphs to model them. These graphs are often dynamic in nature, i.e., the structure of the graph changes with time. The Single Source Shortest Path (SSSP) problem, which finds the shortest distance of all vertices from a source vertex, often appears in different scenarios. In a large-scale dynamic network, finding SSSP becomes challenging due to the rapid structural changes in the graph and scalability issues. Although numerous parallel shortest path algorithms on static networks have been proposed in the literature, the SSSP problem in large-scale dynamic networks requires more attention due to its continual appearances in modern scenarios.

ACM-SRC Semi-Finalist: no

Poster: PDF
Poster Summary: PDF


Back to Poster Archive Listing