Reliable Hubs for PartiallyDynamic AllPairs Shortest Paths in Directed Graphs We give new partiallydynamic algorithms for the allpairs shortest paths problem in weighted directed graphs. Most importantly, we give a new deterministic incremental algorithm for the problem that handles updates in widetildeO(mn43logWepsilon) total time (where the edge weights are from 1,W) and explicitly maintains a (1epsilon)approximate distance matrix. For a fixed epsilonu003e0, this is the first deterministic partially dynamic algorithm for allpairs shortest paths in directed graphs, whose update time is o(n2) regardless of the number of edges. Furthermore, we also show how to improve the stateoftheart partially dynamic randomized algorithms for allpairs shortest paths Baswana et al. STOCu002702, Bernstein STOCu002713 from Monte Carlo randomized to Las Vegas randomized without increasing the running time bounds (with respect to the widetildeO(cdot) notation).  :121,results are obtained by giving new algorithms for the problem of dynamically maintaining hubs, that is a set of widetildeO(nd) vertices which hit a shortest path between each pair of vertices, provided it has hoplength Omega(d). We give new subquadratic deterministic and Las Vegas algorithms for maintenance of hubs under either edge insertions or deletions.

A Supernodal AllPairs Shortest Path Algorithm We show how to exploit graph sparsity in the FW algorithm for the allpairs shortest path (APSP) problem. FW is an attractive choice for APSP on highperforming 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, FW 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 FW and Gaussian elimination, and thereby import several algorithmic techniques from sparse Cholesky factorization, namely, fillin 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 a baseline FW that does not exploit sparsity. Our experiments suggest that FW algorithm can be competitive with Dijkstraxe2x80x99s algorithm (the algorithmic core of Johnsonxe2x80x99s algorithm) for several classes sparse graphs.Npiyush kumar saoOak Ridge National LabRamki KannanOak Ridge National LaboratoryPras