• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Guo, Longkun (Guo, Longkun.) [1] (Scholars:郭龙坤) | Deng, Yunyun (Deng, Yunyun.) [2] | Liao, Kewen (Liao, Kewen.) [3] | He, Qiang (He, Qiang.) [4] | Sellis, Timos (Sellis, Timos.) [5] | Hu, Zheshan (Hu, Zheshan.) [6]

Indexed by:

EI Scopus

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. © 2018 International Joint Conferences on Artificial Intelligence. All right reserved.

Keyword:

Artificial intelligence Graph theory

Community:

  • [ 1 ] [Guo, Longkun]College of Mathematics and Computer Science, Fuzhou University, Fuzhou, Fujian; 350116, China
  • [ 2 ] [Deng, Yunyun]College of Mathematics and Computer Science, Fuzhou University, Fuzhou, Fujian; 350116, China
  • [ 3 ] [Liao, Kewen]Department of Computer Science and Software Engineering, Swinburne University, VIC, Australia
  • [ 4 ] [He, Qiang]Department of Computer Science and Software Engineering, Swinburne University, VIC, Australia
  • [ 5 ] [Sellis, Timos]Department of Computer Science and Software Engineering, Swinburne University, VIC, Australia
  • [ 6 ] [Hu, Zheshan]College of Mathematics and Computer Science, Fuzhou University, Fuzhou, Fujian; 350116, China

Reprint 's Address:

Email:

Show more details

Version:

Related Keywords:

Related Article:

Source :

ISSN: 1045-0823

Year: 2018

Volume: 2018-July

Page: 1456-1462

Language: English

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Online/Total:325/11086971
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1