Computing shortest paths in graphs is one of the most fundamental, widely-studied and widely-used optimization problems on graphs. Classical shortest-path algorithms that have been widely used in the past on smaller graphs are no longer effective on massive graphs that arise in communication, social, and biological networks, the world wide web, and other applications. This project will investigate developing correct and efficient techniques and algorithms for shortest paths to run on currently available parallel-computing systems in a communication-efficient manner. The project will address fundamental and theoretical issues that underpin computation of shortest paths in graphs while also addressing the challenges related to designing correct and efficient algorithms for modern computing platforms. These results will expand the understanding of the algorithmic complexity of this very fundamental problem of computing shortest paths in graphs.
In more detail, the project will investigate the design of efficient shortest-path algorithms under settings that include distributed computations with communication along graph edges, parallel shared-memory PRAM computations, and multithreaded computations with caching. The project will study the related problem of developing efficient dynamic algorithms for shortest paths, where the goal is to update shortest paths when the graph changes over time. Massive graphs that arise in practice are almost invariably sparse, where the number of edges is much smaller than quadratic in the number of vertices. For this reason, the project will focus on developing tools and techniques for correct and efficient shortest path algorithms for sparse graphs, and will investigate the design of efficient and scalable data structures to aid the efficient computation of shortest paths on such graphs.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
