![](/images/graphics-bg.png)
Finding the Shortest Path with Vertex Constraint over Large Graphs
Joint Authors
Yang, Yajun
Hu, Qinghua
Wang, Xin
Li, Zhongfei
Source
Issue
Vol. 2019, Issue 2019 (31 Dec. 2019), pp.1-13, 13 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2019-02-19
Country of Publication
Egypt
No. of Pages
13
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Yang, Yajun& Li, Zhongfei& Wang, Xin& Hu, Qinghua. 2019. Finding the Shortest Path with Vertex Constraint over Large Graphs. Complexity،Vol. 2019, no. 2019, pp.1-13.
https://search.emarefa.net/detail/BIM-1133059
Modern Language Association (MLA)
Yang, Yajun…[et al.]. Finding the Shortest Path with Vertex Constraint over Large Graphs. Complexity No. 2019 (2019), pp.1-13.
https://search.emarefa.net/detail/BIM-1133059
American Medical Association (AMA)
Yang, Yajun& Li, Zhongfei& Wang, Xin& Hu, Qinghua. Finding the Shortest Path with Vertex Constraint over Large Graphs. Complexity. 2019. Vol. 2019, no. 2019, pp.1-13.
https://search.emarefa.net/detail/BIM-1133059
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1133059