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.展开更多
Backgrounds Various models have been applied to predict the trend of the epidemic since the outbreak of COVID-19.Methods:In this study,we designed a dynamic graph model,not for precisely predicting the number of infec...Backgrounds Various models have been applied to predict the trend of the epidemic since the outbreak of COVID-19.Methods:In this study,we designed a dynamic graph model,not for precisely predicting the number of infected cases,but for a glance of the dynamics under a public epidemic emergency situation and of different contributing factors・Results^We demonstrated the impact of asymptomatic transmission in this outbreak and showed the effectiveness of city lockdown to halt virus spread within a city.We further illustrated that sudden emergence of a large number of cases could overwhelm the city medical system,and external medical aids are critical to not only containing the further spread of the virus but also reducing fatality.Conclusions Our model simulation showed that highly populated modern cities are particularly vulnerable and lessons learned in China could facilitate other countries to plan the proactive and decisive actions・We shall pay close attention to the asymptomatic transmission being suggested by rapidly accumulating evidence as dramatic changes in quarantine protocol are required to contain SARS・CoV・2 from spreading globally.展开更多
基金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.
基金This study was supported by the National Key R&D Program of China(Nos.2018YFC0910400,2017YFC0907500,and 2018ZX10302205)the National Natural Science Foundation of China(Nos.61702406,3161372,31701739 and 8191101420)+1 种基金the"World-Class Universities and the Characteristic Development Guidance Funds for the Central Universities",Xi'an Jiaotong University Basic Research and Profession Grant(No.xtr022019003)Shanghai Municipal Science and Technology Major Project(No.2017SHZDZX01).
文摘Backgrounds Various models have been applied to predict the trend of the epidemic since the outbreak of COVID-19.Methods:In this study,we designed a dynamic graph model,not for precisely predicting the number of infected cases,but for a glance of the dynamics under a public epidemic emergency situation and of different contributing factors・Results^We demonstrated the impact of asymptomatic transmission in this outbreak and showed the effectiveness of city lockdown to halt virus spread within a city.We further illustrated that sudden emergence of a large number of cases could overwhelm the city medical system,and external medical aids are critical to not only containing the further spread of the virus but also reducing fatality.Conclusions Our model simulation showed that highly populated modern cities are particularly vulnerable and lessons learned in China could facilitate other countries to plan the proactive and decisive actions・We shall pay close attention to the asymptomatic transmission being suggested by rapidly accumulating evidence as dramatic changes in quarantine protocol are required to contain SARS・CoV・2 from spreading globally.
