The computation of the all-pairs shortest paths is an important graph algorithmic problem.When the graph changes,such as edge deletions/insertions,recalculating the shortest distance of a graph from scratch is costly....The computation of the all-pairs shortest paths is an important graph algorithmic problem.When the graph changes,such as edge deletions/insertions,recalculating the shortest distance of a graph from scratch is costly.In this paper,we investigate how to quickly maintain the shortest distance of the dynamic graph in the distributed memory system.For a distributed system with p processors,the state-of-art algorithm to recompute the shortest distance of a graph with n vertices from scratch requires O(n^(2)/√p)bandwidth cost and O(√plog^(2)p)latency cost.For the insertion of k edges,we give an incremental algorithm with a bandwidth cost of O(nk√p+k^(2))and a latency cost of O(logp).For typical scenarios where k=O(n/√p),the bandwidth and latency costs are reduced by a factor of O(√p)and O(√plogp),respectively.For the deletion of k edges,we give a decremental algorithm with a bandwidth cost of O(nk/√p+k^(2)+n^(2)/log^(3)p+|S|^(2)logp)and a latency cost of O(log^(3)p),where S is the separator size of a constructed graph and is related to the alteration degree of the shortest path of the dynamic graph.When k=O(n/√p)and S=O(n/√p),the bandwidth and latency costs are reduced by a factor of O(√p∕log^(3)p)and O(√p∕logp),respectively.展开更多
基金supported in part by National Natural Science Foundation of China under Grants 61972447 and 61832006.
文摘The computation of the all-pairs shortest paths is an important graph algorithmic problem.When the graph changes,such as edge deletions/insertions,recalculating the shortest distance of a graph from scratch is costly.In this paper,we investigate how to quickly maintain the shortest distance of the dynamic graph in the distributed memory system.For a distributed system with p processors,the state-of-art algorithm to recompute the shortest distance of a graph with n vertices from scratch requires O(n^(2)/√p)bandwidth cost and O(√plog^(2)p)latency cost.For the insertion of k edges,we give an incremental algorithm with a bandwidth cost of O(nk√p+k^(2))and a latency cost of O(logp).For typical scenarios where k=O(n/√p),the bandwidth and latency costs are reduced by a factor of O(√p)and O(√plogp),respectively.For the deletion of k edges,we give a decremental algorithm with a bandwidth cost of O(nk/√p+k^(2)+n^(2)/log^(3)p+|S|^(2)logp)and a latency cost of O(log^(3)p),where S is the separator size of a constructed graph and is related to the alteration degree of the shortest path of the dynamic graph.When k=O(n/√p)and S=O(n/√p),the bandwidth and latency costs are reduced by a factor of O(√p∕log^(3)p)and O(√p∕logp),respectively.
