{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T15:53:34Z","timestamp":1775145214037,"version":"3.50.1"},"reference-count":32,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2019,2,19]],"date-time":"2019-02-19T00:00:00Z","timestamp":1550534400000},"content-version":"vor","delay-in-days":49,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61402323"],"award-info":[{"award-number":["61402323"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61572353"],"award-info":[{"award-number":["61572353"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U1736103"],"award-info":[{"award-number":["U1736103"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Complexity"],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>Graph is an important complex network model to describe the relationship among various entities in real applications, including knowledge graph, social network, and traffic network. Shortest path query is an important problem over graphs and has been well studied. This paper studies a special case of the shortest path problem to find the shortest path passing through a set of vertices specified by user, which is NP\u2010hard. Most existing methods calculate all permutations for given vertices and then find the shortest one from these permutations. However, the computational cost is extremely expensive when the size of graph or given set of vertices is large. In this paper, we first propose a novel exact heuristic algorithm in best\u2010first search way and then give two optimizing techniques to improve efficiency. Moreover, we propose an approximate heuristic algorithm in polynomial time for this problem over large graphs. We prove the ratio bound is 3 for our approximate algorithm. We confirm the efficiency of our algorithms by extensive experiments on real\u2010life datasets. The experimental results validate that our algorithms always outperform the existing methods even though the size of graph or given set of vertices is large.<\/jats:p>","DOI":"10.1155\/2019\/8728245","type":"journal-article","created":{"date-parts":[[2019,2,19]],"date-time":"2019-02-19T23:31:24Z","timestamp":1550619084000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Finding the Shortest Path with Vertex Constraint over Large Graphs"],"prefix":"10.1155","volume":"2019","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0824-2931","authenticated-orcid":false,"given":"Yajun","family":"Yang","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0592-3475","authenticated-orcid":false,"given":"Zhongfei","family":"Li","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9651-0651","authenticated-orcid":false,"given":"Xin","family":"Wang","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7765-8095","authenticated-orcid":false,"given":"Qinghua","family":"Hu","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2019,2,19]]},"reference":[{"key":"e_1_2_12_1_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2018.2797876"},{"key":"e_1_2_12_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2017.2746258"},{"key":"e_1_2_12_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2017.2690664"},{"key":"e_1_2_12_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2016.2602702"},{"key":"e_1_2_12_5_2","first-page":"155","article-title":"Efficiently answering probability threshold-based shortest path queries over uncertain graphs","author":"Yuan Y.","year":"2010","journal-title":"International Conference on Database Systems for Advanced Applications"},{"key":"e_1_2_12_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2518692"},{"key":"e_1_2_12_7_2","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350234"},{"key":"e_1_2_12_8_2","doi-asserted-by":"crossref","unstructured":"RiceM. N.andTsotrasV. J. Exact graph search algorithms for generalized traveling salesman path problems International Symposium on Experimental Algorithms 2012 Springer 344\u2013355.","DOI":"10.1007\/978-3-642-30850-5_30"},{"key":"e_1_2_12_9_2","doi-asserted-by":"crossref","unstructured":"GeisbergerR. SandersP. SchultesD. andDellingD. Contraction hierarchies: Faster and simpler hierarchical routing in road networks International Workshop on Experimental and Efficient Algorithms 2008 Springer 319\u2013333.","DOI":"10.1007\/978-3-540-68552-4_24"},{"key":"e_1_2_12_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_12_11_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"key":"e_1_2_12_12_2","doi-asserted-by":"crossref","unstructured":"LiF. ChengD. HadjieleftheriouM. KolliosG. andTengS. On trip planning queries in spatial databases International Symposium on Spatial and Temporal Databases 2005 Springer 273\u2013290.","DOI":"10.1007\/11535331_16"},{"key":"e_1_2_12_13_2","doi-asserted-by":"crossref","unstructured":"VardhanH. BillenahalliS. HuangW. RazoM. SivasankaranA. TangL. MontiP. TaccaM. andFumagalliA. Finding a simple path with multiple must-include nodes Modeling Analysis & Simulation of Computer and Telecommunication Systems MASCOTS\u201909 2009 IEEE International Symposium on. IEEE 1\u20133.","DOI":"10.1109\/MASCOT.2009.5366808"},{"key":"e_1_2_12_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2017.09.008"},{"key":"e_1_2_12_15_2","volume-title":"Fast Approximations for Metric-Tsp via Linear Programming","author":"Chekuri C.","year":"2018"},{"key":"e_1_2_12_16_2","article-title":"Advances in combinatorial optimization: Linear programming formulations of the traveling salesman and other hard combinatorial optimization problems","author":"Diaby M.","year":"2016","journal-title":"World Scientific"},{"key":"e_1_2_12_17_2","first-page":"64","article-title":"Fuzzy multi-objective linear programming for traveling salesman problem","volume":"4","author":"Chaudhuri A.","year":"2011","journal-title":"African Journal of Mathematics Computer Science Research"},{"key":"e_1_2_12_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2015.01.068"},{"key":"e_1_2_12_19_2","doi-asserted-by":"publisher","DOI":"10.4018\/ijamc.2015010103"},{"key":"e_1_2_12_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-016-1739-2"},{"key":"e_1_2_12_21_2","first-page":"321","article-title":"An approximate algorithm combining p systems and ant colony optimization for taraveling salesman problems","author":"Zhang G.","year":"2010","journal-title":"Miguel Angel Mart\u0142nez Del Amor"},{"key":"e_1_2_12_22_2","article-title":"Generalized traveling salesman problem through n sets of nodes","author":"Srivastava S. S. S.","year":"1969","journal-title":"Cors Journal"},{"key":"e_1_2_12_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2009.10.027"},{"key":"e_1_2_12_24_2","doi-asserted-by":"crossref","unstructured":"TasgetirenM. F. SuganthanP. N. andPanQ. A discrete particle swarm optimization algorithm for the generalized traveling salesman problem Proceedings of the 9th Annual Genetic and Evolutionary Computation Conference (GECCO \u203207) July 2007 New York NY USA 158\u2013167 https:\/\/doi.org\/10.1145\/1276958.1276980 2-s2.0-34548086557.","DOI":"10.1145\/1276958.1276980"},{"key":"e_1_2_12_25_2","doi-asserted-by":"crossref","unstructured":"RiceM. N.andTsotrasV. J. Engineering generalized shortest path queries Proceedings of the 2013 29th IEEE International Conference on Data Engineering (ICDE 2013) April 2013 949\u2013960 https:\/\/doi.org\/10.1109\/ICDE.2013.6544888.","DOI":"10.1109\/ICDE.2013.6544888"},{"key":"e_1_2_12_26_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008779125567"},{"key":"e_1_2_12_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(01)00227-2"},{"key":"e_1_2_12_28_2","article-title":"The traveling salesman problem with separation requirements","volume":"140","author":"Wang X.","year":"2002","journal-title":"European Journal of Operational Research"},{"key":"e_1_2_12_29_2","unstructured":"KaranM.andSkorin-KapovN. A branch and bound algorithm for the sequential ordering problem MIPRO 2011 Proceedings of the 34th International Convention 2011 IEEE 452\u2013457."},{"key":"e_1_2_12_30_2","unstructured":"CaoX. ChenL. CongG. GuanJ. PhanN. andXiaoX. KORS: Keyword-aware optimal route search system 29th IEEE International Conference on Data Engineering ICDE 2013 April 2013 Brisbane Australia 1340\u20131343."},{"key":"e_1_2_12_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-016-1653-3"},{"key":"e_1_2_12_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2509998"}],"container-title":["Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2019\/8728245.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2019\/8728245.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/2019\/8728245","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T12:14:23Z","timestamp":1723032863000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/2019\/8728245"}},"subtitle":[],"editor":[{"given":"Xin","family":"Huang","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1155\/2019\/8728245"],"URL":"https:\/\/doi.org\/10.1155\/2019\/8728245","archive":["Portico"],"relation":{},"ISSN":["1076-2787","1099-0526"],"issn-type":[{"value":"1076-2787","type":"print"},{"value":"1099-0526","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]},"assertion":[{"value":"2018-11-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-31","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-19","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"8728245"}}