GDL

Undergraduate Theses from gdlhub / 2017-08-16 09:09:30
Oleh : R. Kalpana , P. Thambidurai, STIKOM Dinamika Bangsa Jambi
Dibuat : 2014-01-16, dengan 1 file

Keyword : Dijkstra’s algorithm Speedup techniques Dynamic graphs Parallel programming
Url : http://www.sciencedirect.com/science/article/pii/S1319157813000153
Sumber pengambilan dokumen : web

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 speedup in a QPL of 140. The use of the Parallel speedup technique results in an average speedup in a QPL of more than 1 in the planar and road networks.

Beri Komentar ?#(0) | Bookmark

Properti	Nilai Properti
ID Publisher	gdlhub
Organisasi	STIKOM Dinamika Bangsa Jambi
Nama Kontak	Herti Yani, S.Kom
Alamat	Jln. Jenderal Sudirman
Kota	Jambi
Daerah	Jambi
Negara	Indonesia
Telepon	0741-35095
Fax	0741-35093
E-mail Administrator	elibrarystikom@gmail.com
E-mail CKO	elibrarystikom@gmail.com