• Admin
    UC Research Repository
    View Item 
       
    • UC Home
    • Library
    • UC Research Repository
    • College of Engineering
    • Engineering: Theses and Dissertations
    • View Item
       
    • UC Home
    • Library
    • UC Research Repository
    • College of Engineering
    • Engineering: Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Browse

    All of the RepositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    Statistics

    View Usage Statistics

    Improved shortest path algorithms for nearly acyclic graphs

    Thumbnail
    View/Open
    Saunders_S_2004_thesis.pdf (6.629Mb)
    Author
    Saunders, Shane
    Date
    2004
    Permanent Link
    http://hdl.handle.net/10092/12895
    Thesis Discipline
    Computer Science
    Degree Grantor
    University of Canterbury
    Degree Level
    Doctoral
    Degree Name
    Doctor of Philosophy

    Dijkstra's algorithm solves the single-source shortest path problem on any directed graph in O(m+nlogn) worst-case time when a Fibonacci heap is used as the frontier set data structure. Here n is the number of vertices and m is the number of edges in the graph. If the graph is nearly acyclic, then other algorithms can achieve a time complexity lower than that of Dijkstra's algorithm. Abuaiadh and Kingston gave a single source shortest path algorithm for nearly acyclic graphs with O(m + nlogt) worst-case time complexity, where the new parameter t is the number of delete-min operations performed in priority queue manipulation. For nearly acyclic graphs, the value of t is expected to be small, allowing the algorithm to outperform Dijkstra's algorithm. Takaoka, using a different definition for acyclicity, gave an algorithm with 0 ( m + n log k) worstcase time complexity. In this algorithm, the new parameter k is the maximum cardinality of the strongly connected components in the graph. This thesis presents several new shortest path algorithms that define trigger vertices, from which efficient computation of shortest paths through underlying acyclic structures in the graph is possible. Various definitions for trigger vertices are considered. One definition decomposes a graph into a unique set of acyclic structures, where each single trigger vertex dominates a single corresponding acyclic structure. This acyclic decomposition can be computed in O(m) time, thus allowing the single source problem to be solved in 0 ( m + r log r) worst-case time, where r is the resulting 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. It is possible to define both monodirectional and bidirectional variants of this acyclic decomposition. This thesis also presents decompositions in which multiple trigger vertices dominate a single acyclic structure. The trigger vertices of such decompositions constitute feedback vertex sets. If trigger vertices are defined as a set of precomputed feedback vertices, then the all-pairs shortest path problem can be solved in O(mn + nr² ) 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. For suitable graph types, these new algorithms offer an improvement on the time complexity of previous algorithms.

    Collections
    • Engineering: Theses and Dissertations [2165]
    Rights
    https://canterbury.libguides.com/rights/theses

    UC Research Repository
    University Library
    University of Canterbury
    Private Bag 4800
    Christchurch 8140

    Phone
    364 2987 ext 8718

    Email
    ucresearchrepository@canterbury.ac.nz

    Follow us
    FacebookTwitterYoutube

    © University of Canterbury Library
    Send Feedback | Contact Us