CSSE Seminar Series (CSSESS)

Quick links: Past seminars,  future seminars,  CSSESS Home

In 1985, Moffat-Takaoka (MT) algorithm was developed to solve the all pairs shortest path (APSP) problem. This algorithm manages to get time complexity of O(n2 log n) expected time when the end-point independent model of probabilistic assumption is used. However, the use of a critical point introduced in this algorithm has made the implementation of this algorithm quite complicated and the running time of this algorithm is difficult to analyze. Therefore, this study introduces a new deterministic algorithm for the APSP that provides an alternative to the existing MT algorithm. The major advantages of this approach compared to the MT algorithm are its simplicity, intuitive appeal and ease of analysis. Moreover, the algorithm was shown to be efficient as the expected running time is the same O(n2 log n). Performance of a good algorithm depends on the data structure used to speed up the operations needed by the algorithm such as insert, delete-min and decrease-key operations. In this study, two new data structures also have been implemented, namely quaternary and dimensional heaps. In the experiment carried out, the quaternary heap that employed similar concept with the rinomial heap with a special insertion cache function performed better than the trinomial heap when the number of n vertices was small. Likewise, the dimensional heap data structure executed the decrease-key operation efficiently by maintaining the thinnest structure possible through the use of thin and thick edges, far surpassing the existing binary, Fibonacci and 2-3 heaps data structures when a special acyclic graph was used. Taken together all these promising findings, a new improved algorithm running on a good data structure can be implemented to enhance the computing accuracy and speed of todays computing machines.

Mashitoh Binti Hashim is currently a lecturer at Sultan Idris Education University in Malaysia. She received her undergraduate degree in Information Technology, majoring in Computer Science from the National University of Malaysia. She was then awarded a scholarship from Tun Razak University to pursue her Master’s degree at the same university, majoring in Software Engineering. Mashi managed to get a scholarship from the Ministry of Higher Education of Malaysia which enabled her to continue her studies at the PhD level in Algorithm and Data Structure research area at University of Canterbury. The topic that she is going to present is her PhD research title under Prof. Tad’s supervision.

Quick links: Past seminars,  future seminars,  CSSESS Home