Efficient Parallel Algorithm for Shortest Path Updates in Dynamic Networks at Scale
Event Type
ACM Student Research Competition: Graduate Poster
ACM Student Research Competition: Undergraduate Poster
Posters
In-Person Only
TP
XO / EX
TimeTuesday, 16 November 20218:30am - 5pm CST
LocationSecond Floor Atrium
DescriptionThe 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.
Archive view