{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T15:28:53Z","timestamp":1769527733517,"version":"3.49.0"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,7]]},"abstract":"<jats:p>The classical disjoint shortest path problem has recently recalled\n\ninterests from researchers in the network planning and optimization\n\ncommunity. However, the requirement of the shortest paths being completely\n\nvertex or edge disjoint might be too restrictive and demands much\n\nmore resources in a network. Partially disjoint shortest paths, in\n\nwhich a bounded number of shared vertices or edges is allowed, balance\n\nbetween degree of disjointness and occupied network resources.\n\n\n\nIn this paper, we consider the problem of finding k \n\nshortest paths which are edge disjoint but partially vertex disjoint.\n\nFor a pair of distinct vertices in a network graph, the problem aims\n\nto optimally find k edge disjoint shortest paths among which\n\nat most a bounded number of vertices are shared by at least two paths. In particular,\n\nwe present novel techniques for exactly solving the problem\n\nwith a runtime  that  significantly improves\n\nthe current best result. The\n\nproposed algorithm is also validated by computer experiments on both\n\nsynthetic and real networks which demonstrate its superior efficiency\n\nof up to three orders of magnitude faster than the state of the art.<\/jats:p>","DOI":"10.24963\/ijcai.2018\/202","type":"proceedings-article","created":{"date-parts":[[2018,7,5]],"date-time":"2018-07-05T01:49:10Z","timestamp":1530755350000},"page":"1456-1462","source":"Crossref","is-referenced-by-count":13,"title":["A Fast Algorithm for Optimally Finding Partially Disjoint Shortest Paths"],"prefix":"10.24963","author":[{"given":"Longkun","family":"Guo","sequence":"first","affiliation":[{"name":"College of Mathematics and Computer Science, Fuzhou University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yunyun","family":"Deng","sequence":"additional","affiliation":[{"name":"College of Mathematics and Computer Science, Fuzhou University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kewen","family":"Liao","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Software Engineering, Swinburne University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qiang","family":"He","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Software Engineering, Swinburne University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timos","family":"Sellis","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Software Engineering, Swinburne University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zheshan","family":"Hu","sequence":"additional","affiliation":[{"name":"College of Mathematics and Computer Science, Fuzhou University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10584","event":{"name":"Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}","theme":"Artificial Intelligence","location":"Stockholm, Sweden","acronym":"IJCAI-2018","number":"27","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2018,7,13]]},"end":{"date-parts":[[2018,7,19]]}},"container-title":["Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2018,7,5]],"date-time":"2018-07-05T01:50:57Z","timestamp":1530755457000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2018\/202"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2018,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2018\/202","relation":{},"subject":[],"published":{"date-parts":[[2018,7]]}}}