报告题目：Fast Algorithms for Optimally Finding Partially Disjoint Shortest Paths
The classical disjoint shortest path problem has recently recalled interests from researchers in the networks planning and optimization community. However, the requirement of the shortest paths being completely vertex or edge disjoint might be too restrictive and demands much more resources in a network. Partial disjoint shortest paths, in which a bounded number of shared vertices or edges is allowed, balance between degree of disjointness and occupied network resources. In this paper, we consider the δ-vertex k edge-disjoint shortest path problem (δV-kEDSP), that is, for a pair of distinct vertices in a network graph, it optimally finds k edge-disjoint shortest paths between them where at most δ vertices are shared by at least two paths. We present techniques for exactly solving δV-2EDSP with runtime O(δm+n log n), which significantly improves the O(mn^2+n^3\log n) runtime bound of the state-of-art. The proposed theoretical approaches are also validated by computer experiments on both synthetic and real networks which demonstrate their superior efficiency of up to three orders of magnitude faster than the state-of-art solution.
郭龙坤，博士，福州大学数学与计算机科学学院副教授，福州大学旗山学者．主要研究领域为并行分布式计算与高性能计算机网络相关的组合优化应用及算法设计与分析．长期以来从事路径、网络数据传输与资源调度领域的研究工作．在IEEE transactions on mobile computing(TMC), IEEE transactions on computers(TC), Algorithmica, IEEE transactions on parallel and distributed systems (TPDS)等国际期刊及ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)，IJCAI等国际会议发表论文三十余篇．担任PDCAT, PAAP与Cloud-asia等并行与分布式计算领域会议的委员会成员(PC Member)．当前主持一项国家自然科学面上基金，已完成一项国家基金与多项省部基金．