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
 
    

Efficient Algorithms for Solving Shortest Paths on Nearly Acyclic Directed Graphs

Saunders, S. and Takaoka, T.

    This paper presents new algorithms for computing shortest paths in a nearly acyclic directed graph G = (V,E). The new algorithms improve on the worst-case running time of previous algorithms. Such algorithms use the concept of a 1-dominator set. A 1-dominator set divides the graph into a unique collection of acyclic subgraphs, where each acyclic subgraph is dominated by a single associated trigger vertex. The previous time for computing a 1-dominator set is improved from O(mn) to O(m), where m = |E| and n = |V|. Efficient shortest path algorithms only spend delete-min operations on trigger vertices, thereby making the computation of shortest paths through non-trigger vertices easier. Under this framework, the time complexity for the all-pairs shortest path (APSP) problem is improved from O(mn + nr log r) to O(mn + r2 log r), where r is the number of triggers. Here the second term in the complexity results from delete-min operations in a heap of size r. The time complexity of the APSP problem on the broader class of nearly acyclic graphs, where trigger vertices correspond to any precomputed feedback vertex set, is similarly improved from O(mn + nr2) to O(mn + r3). This paper also mentions that the 1-dominator set concept can be generalised to de fine a bidirectional 1-dominator set and k-dominator sets.
Cite as: Saunders, S. and Takaoka, T. (2005). Efficient Algorithms for Solving Shortest Paths on Nearly Acyclic Directed Graphs. In Proc. Eleventh Computing: The Australasian Theory Symposium (CATS2005), Newcastle, Australia. CRPIT, 41. Atkinson, M. and Dehne, F., Eds. ACS. 127-131.
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