CSSE Seminar Series (CSSESS)
Welcome to the web page describing past, present, and future seminars presented by staff, students, and visitors to the Department of Computer Science and Software Engineering.
View past or future seminars; or view the CSSESS Home Page.
Seminar
Improved Shortest Path Algorithms for Nearly Acyclic Graphs.
Speaker: Shane Saunders, PhD student.
Institute: Computer Science Department, University of Canterbury.
Time/Place: 10:00 AM, Wed, 3 Sep, in Room 031, Erskine Building.
Abstract
Dijkstra's algorithm solves the single-source shortest path problem on any directed graph of n vertices and m edges in O(m + n log n) worst case time when using a Fibonacci heap as the frontier set data structure. If the graph is nearly acyclic, other algorithms can achieve a worst case time complexity lower than that of Dijkstra's algorithm. This seminar presents the results of Ph.D. thesis research, including several new shortest path algorithms for nearly acyclic graphs.
The new algorithms define trigger vertices from which shortest paths are efficiently computed through underlying acyclic structures in the graph. Trigger vertices can be defined in various ways. Several definitions allow the single source problem to be solved in O(m + r log r) worst case time, where r is the number of trigger vertices in the graph. For nearly acyclic graphs, the value of r is small and single-source can be solved in close to O(m) worst case time. If trigger vertices are defined as a set of pre-computed feedback vertices, then the all-pairs shortest path problem can be solved in O(mn + nr^2) worst case time. This allows all-pairs to be solved in O(mn) worst case time when a feedback vertex set smaller than the square root of the number of edges is known.
Biography
View past or future seminars; or view the CSSESS Home Page.