Article - Main Track

Intersection of longer paths in some graph classes: theoretical results, implementation and execution of algorithms.

Author: ALMEIDA, G. M. F., DIAS, E. S.

Abstract: In this paper, we study the longest paths and their intersections in chordal graphs, weighted graphs, trees and complementary prism graphs. Theoretical results were obtained about the longest paths and their intersections and some factorial time algorithms in order to understand the problem and the behavior of the longest paths in the different graph types. Finally, we analyze the implementation of the algorithms and the tests made in the laboratory, showing the execution time and its performance given different graph sizes, where the reader can conclude the algorithms effciency and providing the test results for new ones. comparisons with future algorithms. This work is one of the results of a scientific initiation by the authors.

Keywords: Longest paths, graph products, algorithms, intersection of paths.

Full paper (in Portuguese)

Referência completa: Almeida, G. M. F., Dias, E. S., "Intersecção de caminhos mais longos em algumas classes de grafos: resultados teóricos, implementação e execução de algoritmos", Revista de Sistemas de Informação da FSMA n 24(2019) pp. 55-66

Back