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

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