2020 · 20 citations · 31 references
ComputingComputer ScienceMathematicsAlgorithmsParallel AlgorithmsParallel ComputingAlgorithm AnalysisData ParallelismGraph AlgorithmsMatrix ComputationMatrix FactorizationShortest Path AlgorithmsAll-pairs Shortest PathsFloyd-warshall AlgorithmGaussian EliminationJohnson's AlgorithmMatrix MultiplicationShared MemoryShortest Path ProblemsSymbolic Analysis
We show how to exploit graph sparsity in the Floyd-Warshall algorithm for the all-pairs shortest path (Apsp) problem. Floyd-Warshall is an attractive choice for Apsp on high-performing systems due to its structural similarity to solving dense linear systems and matrix multiplication. However, if sparsity of the input graph is not properly exploited, Floyd-Warshall will perform unnecessary asymptotic work and thus may not be a suitable choice for many input graphs. To overcome this limitation, the key idea in our approach is to use the known algebraic relationship between Floyd-Warshall and Gaussian elimination, and import several algorithmic techniques from sparse Cholesky factorization, namely, fill-in reducing ordering, symbolic analysis, supernodal traversal, and elimination tree parallelism. When combined, these techniques reduce computation, improve locality and enhance parallelism. We implement these ideas in an efficient shared memory parallel prototype that is orders of magnitude faster than an efficient multi-threaded baseline Floyd-Warshall that does not exploit sparsity. Our experiments suggest that the Floyd-Warshall algorithm can compete with Dijkstra's algorithm (the algorithmic core of Johnson's algorithm) for several classes sparse graphs.
31
Expander graphs and their applications
Shlomo Hoory, Nathan Linial, Avi Wigderson · Bulletin of the American Mathematical Society · 2006 · 1.8K citations · Full text
A Separator Theorem for Planar Graphs
Richard J. Lipton, Robert E. Tarjan · SIAM Journal on Applied Mathematics · 1979 · 1.4K citations
Efficient Algorithms for Shortest Paths in Sparse Networks
D. Barton Johnson · Journal of the ACM · 1977 · 1K citations · Full text