Now showing items 1-2 of 2
Improved Shortest Path Algorithms for Nearly Acyclic Graphs
(University of Canterbury, 2002)
Dijkstra’s algorithm solves the single-source shortest path problem on any directed graph in O(m + n log n) time when a Fibonacci heap is used as the frontier set data structure. Here n is the number of vertices and m ...
Solving Shortest Paths Efficiently on Nearly Acyclic Directed Graphs
(University of Canterbury, 2006)
Shortest path problems can be solved very efficiently when a directed graph is nearly acyclic. Earlier results defined a graph decomposition, now called the 1-dominator set, which consists of a unique collection of acyclic ...