Conferences in Research and Practice in Information Technology
  

Online Version - Last Updated - 20 Jan 2012

 

 
Home
 

 
Procedures and Resources for Authors

 
Information and Resources for Volume Editors
 

 
Orders and Subscriptions
 

 
Published Articles

 
Upcoming Volumes
 

 
Contact Us
 

 
Useful External Links
 

 
CRPIT Site Search
 
    

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
 

 

ACS Logo© Copyright Australian Computer Society Inc. 2001-2014.
Comments should be sent to the webmaster at crpit@scem.uws.edu.au.
This page last updated 16 Nov 2007