Academic Journals Database
Disseminating quality controlled scientific knowledge

Combining Speedup Techniques based on Landmarks and Containers with parallelised preprocessing in Random and Planar Graphs

Author(s): R. Kalpana | P. Thambidurai

Journal: International Journal of Computer Science & Information Technology
ISSN 0975-4660

Volume: 3;
Issue: 1;
Start page: 152;
Date: 2011;
VIEW PDF   PDF DOWNLOAD PDF   Download PDF Original page

Keywords: Dijkstra’s Algorithm | Graph Theory | parallel execution | speed-up

The Dijkstra’s algorithm is applied in many real world problems like mobile routing, road maps,railway networks, etc,. There are many techniques available to speedup the algorithm while guaranteeingthe optimality of the solution. Almost all of the speedup techniques have a substantial amount of parallelism that can be exploited to decrease its running time. By suitably modifying portions of theexisting system various degrees of parallelism can be achieved. The rapidly growing field of multiprocessing systems and multi-core processors provide many opportunities for such improvements. Inthese techniques there’s always a demand for the running time and the time required for pre-processing.Space requirements for the pre-processing also have a major influence on the running time of thealgorithm. The main focus of the work is to implement landmark technique and to identify the segment of the code in landmark pre-processing which can be parallelized to obtain better speedup. The results are applied to the combined speedup technique which is based on landmarks and containers. The experimental results were compared and analysed for determining better performance improvements in random graphs and planar graphs.
Why do you need a reservation system?      Save time & money - Smart Internet Solutions