IDEAS home Printed from https://ideas.repec.org/a/hin/complx/8728245.html
   My bibliography  Save this article

Finding the Shortest Path with Vertex Constraint over Large Graphs

Author

Listed:
  • Yajun Yang
  • Zhongfei Li
  • Xin Wang
  • Qinghua Hu

Abstract

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-hard. 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-first 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-life 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.

Suggested Citation

  • Yajun Yang & Zhongfei Li & Xin Wang & Qinghua Hu, 2019. "Finding the Shortest Path with Vertex Constraint over Large Graphs," Complexity, Hindawi, vol. 2019, pages 1-13, February.
    • Handle: RePEc:hin:complx:8728245
    DOI: 10.1155/2019/8728245
    as

    Download full text from publisher

    File URL: http://downloads.hindawi.com/journals/8503/2019/8728245.pdf
    Download Restriction: no
    File URL: http://downloads.hindawi.com/journals/8503/2019/8728245.xml
    Download Restriction: no
    File URL: https://libkey.io/10.1155/2019/8728245?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Yong Wang, 2015. "An Approximate Algorithm for Triangle TSP with a Four-Vertex-Three-Line Inequality," International Journal of Applied Metaheuristic Computing (IJAMC), IGI Global, vol. 6(1), pages 35-46, January.
    2. Moon, Chiung & Kim, Jongsoo & Choi, Gyunghyun & Seo, Yoonho, 2002. "An efficient genetic algorithm for the traveling salesman problem with precedence constraints," European Journal of Operational Research, Elsevier, vol. 140(3), pages 606-617, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mina Roohnavazfar & Seyed Hamid Reza Pasandideh, 2022. "Decomposition algorithm for the multi-trip single vehicle routing problem with AND-type precedence constraints," Operational Research, Springer, vol. 22(4), pages 4253-4285, September.
    2. Carter, Arthur E. & Ragsdale, Cliff T., 2006. "A new approach to solving the multiple traveling salesperson problem using genetic algorithms," European Journal of Operational Research, Elsevier, vol. 175(1), pages 246-257, November.
    3. Merve Kayacı Çodur & Mustafa Yılmaz, 2020. "A time-dependent hierarchical Chinese postman problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 28(1), pages 337-366, March.
    4. Gustavo Erick Anaya Fuentes & Eva Selene Hernández Gress & Juan Carlos Seck Tuoh Mora & Joselito Medina Marín, 2018. "Solution to travelling salesman problem by clusters and a modified multi-restart iterated local search metaheuristic," PLOS ONE, Public Library of Science, vol. 13(8), pages 1-20, August.
    5. Kaj Holmberg, 2019. "The (Over)zealous Snow Remover Problem," Transportation Science, INFORMS, vol. 53(3), pages 867-881, May.
    6. Carter, Arthur E. & Ragsdale, Cliff T., 2009. "Quality inspection scheduling for multi-unit service enterprises," European Journal of Operational Research, Elsevier, vol. 194(1), pages 114-126, April.
    7. Nikolakopoulos, Athanassios & Sarimveis, Haralambos, 2007. "A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1911-1929, March.
    8. Abdullah Falih & Ahmed Z. M. Shammari, 2020. "Hybrid constrained permutation algorithm and genetic algorithm for process planning problem," Journal of Intelligent Manufacturing, Springer, vol. 31(5), pages 1079-1099, June.
    9. Qin, Hu & Zhang, Zizhen & Qi, Zhuxuan & Lim, Andrew, 2014. "The freight consolidation and containerization problem," European Journal of Operational Research, Elsevier, vol. 234(1), pages 37-48.
    10. Yuliang Su & Xuening Chu & Dongping Chen & Xiwu Sun, 2018. "A genetic algorithm for operation sequencing in CAPP using edge selection based encoding strategy," Journal of Intelligent Manufacturing, Springer, vol. 29(2), pages 313-332, February.
    11. Izabela Nielsen & Quang-Vinh Dang & Grzegorz Bocewicz & Zbigniew Banaszak, 2017. "A methodology for implementation of mobile robot in adaptive manufacturing environments," Journal of Intelligent Manufacturing, Springer, vol. 28(5), pages 1171-1188, June.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:hin:complx:8728245. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Mohamed Abdelhakeem (email available below). General contact details of provider: https://www.hindawi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.