| LEADER |
02397nam a22002417a 4500 |
| 001 |
1715943 |
| 024 |
|
|
|3 10.33948/0584-026-001-011
|
| 041 |
|
|
|a eng
|
| 044 |
|
|
|b السعودية
|
| 100 |
|
|
|9 524598
|a Kalpana, R.
|e Author
|
| 245 |
|
|
|a A Speedup Technique For Dynamic Graphs Using Partitioning Strategy And Multithreaded Approach
|
| 260 |
|
|
|b جامعة الملك سعود
|c 2014
|
| 300 |
|
|
|a 111 - 119
|
| 336 |
|
|
|a بحوث ومقالات
|b Article
|
| 520 |
|
|
|b There are many pre-processing-based speedup techniques for shortest path problems that are available in the literature. These techniques have an increased demand because of large datasets in such applications such as roadmaps, web search engines and mobile data sets. Pre-processing for the Time-Dependent Shortest Path Problem is still a demanding process that involves graph or network partitioning strategy. Efficient pre-processing of graphs or networks reduces the shortest path computation time while parallelizing the pre-processing phase improves the speedup of the system. In this paper, a speedup technique called Recursive Spectral Bisection (RSB) combined with the Elliptic Convolution of the shortest path method is proposed for dynamic Time-Dependent networks. The same method has been parallelized, and the results are tested on three types of graphs. It is observed that the Time-Dependent RSB combined with the Elliptic Convolution of the shortest path method has no update time, and the Query Performance Loss (QPL) is reduced in planar and road networks compared to random networks. In road networks, the proposed method achieves an average speed up in a QPL of 140. The use of the Parallel speedup technique results in an average speed up in a QPL of more than 1 in the planar and road networks.
|
| 653 |
|
|
|a الرسوم البيانية
|a شبكات الطرق
|a محركات البحث
|
| 692 |
|
|
|b Dijkstra’s Algorithm
|b Speedup Techniques
|b Dynamic Graphs
|b Parallel Programming
|
| 700 |
|
|
|9 524600
|a Thambidurai, P.
|e Co-Author
|
| 773 |
|
|
|c 011
|e Journal of King Saud University (Computer and Information Sciences)
|f Maǧalaẗ ǧamʼaẗ al-malīk Saud : ùlm al-ḥasib wa al-maʼlumat
|l 001
|m مج26, ع1
|o 0584
|s مجلة جامعة الملك سعود - علوم الحاسب والمعلومات
|v 026
|x 1319-1578
|
| 856 |
|
|
|u 0584-026-001-011.pdf
|
| 930 |
|
|
|d y
|p y
|
| 995 |
|
|
|a science
|
| 999 |
|
|
|c 973038
|d 973038
|
