首页
学院新闻
学院公告
学术信息
就业信息

福州大学郭龙坤副教授学术报告

来源: 点击: 时间: 2018年11月09日 14:57

报告题目:Fast Algorithms for Optimally Finding Partially Disjoint Shortest Paths

报告时间:2018年11月11日上午11:00

报告地点:校本部升华后楼215

报告简介:

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).当前主持一项国家自然科学面上基金,已完成一项国家基金与多项省部基金.


返回首页

上一条:浙江大学张国川教授学术报告

下一条:清华大学张靖副教授学术报告