Improved Shortest Path Algorithms For Nearly Acyclic Directed Graphs

Tian, L. and Takaoka, T.

    This paper presents new algorithms for computing single source shortest paths (SSSPs) in a nearly acyclic directed graph G. The first part introduces higher-order decomposition. This decomposition is an extension of the technique of strongly connected component (sc-component) decomposition. The second part presents a new method for measuring acyclicity based on modifications to two existing methods. In the new method, we decompose the graph into a 1-dominator set, which is a set of acyclic subgraphs where each subgraph is dominated by one trigger vertex. Meanwhile we compute sc-components of a degenerated graph derived from triggers. Using this preprocessing, a new SSSP algorithm has O(m + r logl ) time complexity, where r is the size of the 1-dominator set, and l is the size of the largest sc-component. In the third part, we modify the concept of a 1-dominator set to that of a 1-2-dominator set. Each of acyclic subgraphs obtained by the 1-2-dominator decomposition are dominated by one or two trigger vertices cooperatively. Such subgraphs are potentially larger than those decomposed by the 1-dominator set. Thus fewer trigger vertices are needed to cover the graph.
Cite as: Tian, L. and Takaoka, T. (2007). Improved Shortest Path Algorithms For Nearly Acyclic Directed Graphs. In Proc. Thirtieth Australasian Computer Science Conference (ACSC2007), Ballarat Australia. CRPIT, 62. Dobbie, G., Ed. ACS. 15-24.
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS