http://swrc.ontoware.org/ontology#Article
An Algorithm for Generating All The Directed Paths and Its Application
en
Department of Electronic Engineering Faculty of Engineering University of Osaka
Department of Electronic Engineering Faculty of Engineering University of Osaka
Department of Electronic Engineering Faculty of Engineering University of Osaka
Department of Electronic Engineering Faculty of Engineering University of Osaka
AmTranDinh
Shuji Tsukiyama
Isao Shirakawa
Hiroshi Ozaki
An algorithm to generate all the directed paths from a specified vertex to an-other one in a given graph is proposed. The algorithm requires the processing tine bounded by the order O( (n+m) (p+1) ) and memory space bounded by O(n+m) where n m and p denote the numbers of vertices edges and directed paths in a given graph respectively. As an application of the algorithm the shortest or longest path problem in a directed graph containing cycles of negative weight is also considered.
An algorithm to generate all the directed paths from a specified vertex to an-other one in a given graph is proposed. The algorithm requires the processing tine bounded by the order O( (n+m) (p+1) ) and memory space bounded by O(n+m) , where n, m, and p denote the numbers of vertices, edges, and directed paths in a given graph, respectively. As an application of the algorithm, the shortest or longest path problem in a directed graph containing cycles of negative weight is also considered.
AA00674393
Information Processing in Japan
16
0
31-35
1976-01-01