article · SMARTech Repository (Georgia Institute of Technology) · 2019
Accurately and Efficiently Estimating Dynamic Point-to-Point Shortest Path
Tripathy, Alok
Cited by 0Abstract and details only
Abstract
Point-to-point shortest path (PPSP), or s-t connectivity, is a\nvariant of the shortest path problem found in graph theory. In\nthis problem, we are given a graph and pairs of vertices over\ntime, and the output is the shortest path between each pair\nof vertices. In this paper, we present two algorithms. Our first\nalgorithm approximately solves the PPSP problem on any\narbitrary graph. For each pair of vertices queried, it accurately\nand efficiently estimates the shortest path between the two\nvertices. Our second algorithm extends the first to work on\ndynamic graphs. That is, our second algorithm can efficiently\naccount for changes in the graph, such as friend requests\non the Facebook network or road closures on road networks.\nAt a high level, both algorithms partition the graph into\nhighly connected communities. To respond to a query q(u, v),\nthey each find the fewest number of partitions between u\nand v, and the shortest path through each partition. We\nshow that our static graph algorithm can approximate the\ndistance between two vertices with about 20% − 35% percent\nerror and anywhere from 80X − 70000X faster than a BFS\nin practice with the right choice of partitions. Additionally,\nwe show that our dynamic graph algorithm can account for\nupdates to the graph anywhere from 20X − 20000X faster\nthan rerunning the static graph algorithm for each change to\nthe graph.
Cite this paper
Tripathy, A. (2019). Accurately and Efficiently Estimating Dynamic Point-to-Point Shortest Path. SMARTech Repository (Georgia Institute of Technology).
Tripathy, Alok. “Accurately and Efficiently Estimating Dynamic Point-to-Point Shortest Path.” SMARTech Repository (Georgia Institute of Technology), 2019.
Tripathy, Alok. 2019. “Accurately and Efficiently Estimating Dynamic Point-to-Point Shortest Path.” SMARTech Repository (Georgia Institute of Technology).
Tripathy, A. (2019) ‘Accurately and Efficiently Estimating Dynamic Point-to-Point Shortest Path’, SMARTech Repository (Georgia Institute of Technology).
@article{tripathy2019accurately,
title = {{Accurately and Efficiently Estimating Dynamic Point-to-Point Shortest Path}},
author = {Tripathy, Alok},
journal = {SMARTech Repository (Georgia Institute of Technology)},
year = {2019}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.