Página 1 dos resultados de 14568 itens digitais encontrados em 0.021 segundos
Resultados filtrados por Publicador: Instituto Politécnico do Cávado e do Ave

APAC: An exact algorithm for retrieving cycles and paths in all kinds of graphs

Simões,Ricardo
Fonte: Instituto Politécnico do Cávado e do Ave Publicador: Instituto Politécnico do Cávado e do Ave
Tipo: Artigo de Revista Científica Formato: text/html
Publicado em 01/12/2009 EN
Relevância na Pesquisa
36.72%
This paper presents an alorithm for retrieving all paths and all cycles between two vertices in random directed or undirected connected graphs. This algorithm can be easily implemented and is highly modular; with minor changes it can be adapted to obtain different parameters from the graphs. It is also demonstrated that the complexity of the algorithm increases linearly with the number of paths. The algorithm can be used in a myriad of applications. Aside from calculating all the paths and cycles in a graph, it can be used to calculate all the paths with length l between two vertices in the graph, as well as a solution to the clique decision problem. Thus, it has applications in computer networks, material science and electric networks, as well as in any problem where it is necessary to know the number of paths (not the optimal paths) in a directed or undirected connected graph or in multigraphs. The algorithms currently available in the literature, such as the depth-first search (DFS), are unable to solve this type of problems in a straightforward way.