A fast algorithm for optimally finding partially disjoint shortest paths

Longkun Guo, Yunyun Deng, Kewen Liao, Qiang He, Timos Sellis, Zheshan Hu

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedings

Abstract

The classical disjoint shortest path problem has recently recalled interests from researchers in the network 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. Partially 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 problem of finding k shortest paths which are edge disjoint but partially vertex disjoint. For a pair of distinct vertices in a network graph, the problem aims to optimally find k edge disjoint shortest paths among which at most a bounded number of vertices are shared by at least two paths. In particular, we present novel techniques for exactly solving the problem with a runtime that significantly improves the current best result. The proposed algorithm is also validated by computer experiments on both synthetic and real networks which demonstrate its superior efficiency of up to three orders of magnitude faster than the state of the art.

Original languageEnglish
Title of host publicationProceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018
EditorsJerome Lang
PublisherInternational Joint Conferences on Artificial Intelligence
Pages1456-1462
Number of pages7
Volume2018-July
ISBN (Electronic)9780999241127
DOIs
Publication statusPublished - Jul 2018
Event27th International Joint Conference on Artificial Intelligence, IJCAI 2018 - Stockholm, Sweden
Duration: 13 Jul 201819 Jul 2018

Conference

Conference27th International Joint Conference on Artificial Intelligence, IJCAI 2018
CountrySweden
CityStockholm
Period13/07/1819/07/18

Fingerprint Dive into the research topics of 'A fast algorithm for optimally finding partially disjoint shortest paths'. Together they form a unique fingerprint.

  • Cite this

    Guo, L., Deng, Y., Liao, K., He, Q., Sellis, T., & Hu, Z. (2018). A fast algorithm for optimally finding partially disjoint shortest paths. In J. Lang (Ed.), Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018 (Vol. 2018-July, pp. 1456-1462). International Joint Conferences on Artificial Intelligence. https://doi.org/10.24963/ijcai.2018/202