Finding the Shortest Path with Vertex Constraint over Large Graphs
المؤلفون المشاركون
Yang, Yajun
Hu, Qinghua
Wang, Xin
Li, Zhongfei
المصدر
العدد
المجلد 2019، العدد 2019 (31 ديسمبر/كانون الأول 2019)، ص ص. 1-13، 13ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2019-02-19
دولة النشر
مصر
عدد الصفحات
13
التخصصات الرئيسية
الملخص 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.
نمط استشهاد جمعية علماء النفس الأمريكية (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
نمط استشهاد الجمعية الأمريكية للغات الحديثة (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
نمط استشهاد الجمعية الطبية الأمريكية (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
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-1133059
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر