A fast algorithm for optimally finding partially disjoint shortest paths

Conference item


Guo, Longkun, Deng, Yunyun, Liao, Kewen, He, Qiang, Sellis, Timos and Hu, Zheshan 2018. A fast algorithm for optimally finding partially disjoint shortest paths. Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18), Stockholm, Sweden, July 13-19, 2018. Stockholm, Sweden: International Joint Conferences on Artificial Intelligence. pp. 1456 - 1462 https://doi.org/10.24963/ijcai.2018/202
AuthorsGuo, Longkun, Deng, Yunyun, Liao, Kewen, He, Qiang, Sellis, Timos and Hu, Zheshan
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.

KeywordsMultidisciplinary Topics and Applications: Databases; Heuristic Search and Game Playing: Combinatorial Search and Optimisation; Multidisciplinary Topics and Applications: AI and the Web
Year2018
JournalProceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
PublisherInternational Joint Conferences on Artificial Intelligence
Digital Object Identifier (DOI)https://doi.org/10.24963/ijcai.2018/202
Scopus EID2-s2.0-85049684782
Open accessOpen access
Publisher's version
Page range1456 - 1462
Research GroupPeter Faber Business School
Place of publicationStockholm, Sweden
Permalink -

https://acuresearchbank.acu.edu.au/item/85y87/a-fast-algorithm-for-optimally-finding-partially-disjoint-shortest-paths

  • 0
    total views
  • 0
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as

Related outputs

Temporal betweenness centrality in dynamic graphs
Tsalouchidou, Ioanna, Baeza-Yates, Ricardo, Bonchi, Francesco, Liao, Kewen and Sellis, Timos 2020. Temporal betweenness centrality in dynamic graphs. International Journal of Data Science and Analytics. 9 (3), pp. 257 - 272. https://doi.org/10.1007/s41060-019-00189-x
Contextual community search over large social networks
Chen, Lu, Liu, Chengfei, Liao, Kewen, Li, Jianxin and Zhou, Rui 2019. Contextual community search over large social networks. 35th International Conference on Data Engineering (ICDE). Macao, China: IEEE Computer Society. pp. 88 - 99 https://doi.org/10.1109/ICDE.2019.00017
A cost model for long-term compressed data retention
Liao, Kewen, Moffat, Alistair, Petri, Matthias and Wirth, Anthony 2017. A cost model for long-term compressed data retention. 10th International Conference on Web Search and Data Mining. United States of America: Association for Computing Machinery. pp. 241 - 249 https://doi.org/10.1145/3018661.3018738
Edge labeling schemes for graph data
Goonetilleke, Oshini, Koutra, Danai, Sellis, Timos and Liao, Kewen 2017. Edge labeling schemes for graph data. 29th International Conference on Scientific and Statistical Database Management. United States of America: Association for Computing Machinery. pp. 1 - 12 https://doi.org/10.1145/3085504.3085516
Effective construction of relative Lempel-Ziv dictionaries
Liao, Kewen, Petri, Matthias, Moffat, Alistair and Wirth, Anthony 2016. Effective construction of relative Lempel-Ziv dictionaries. WWW '16: 25th International World Wide Web Conference. Switzerland: Association for Computing Machinery. pp. 807 - 816 https://doi.org/10.1145/2872427.2883042
Effect of off-zenith observations on reducing the impact of precipitation on ground-based microwave radiometer measurement accuracy
Xu, Guirong, Stick Ware, Randolph, Zhang, Wengang, Feng, Guangliu, Liao, Kewen and Liu, Yibing 2014. Effect of off-zenith observations on reducing the impact of precipitation on ground-based microwave radiometer measurement accuracy. Atmospheric Research. 140-141, pp. 85 - 94. https://doi.org/10.1016/j.atmosres.2014.01.021