The Number Of Paths With Length Constraint

The graph theory is developed rapidly and widely in recent years. It is the earliest traceableto some mathematical games problem research, as well as in some of the popular puzzle game.With the development of science, graph theory showing more and more effect on solvingengineering, operations research, network theory, information theory, control theory, gametheory and computer science and other areas of the problem. For such a discipline with a widerange of application, it contains a lot of content.The problem of Simple Paths with Length Constraint (SPLC) is to calculate the number ofsimple paths between two vertices under the length constraint m in the graph. It is a special caseof the k-path problem. In this paper,we first discuss the problem of Non-Simple Paths withLength Constaint in Undirected Graphs (NPLC in UGs) before study of the Simple Paths withLength Constraint in DAGs (SPLC in DAGs) and proposes an algorithm named Nettree forNon-simple Paths with Length Constraint in Undirected Graphs (NNPLCUG) based on thenettree data structure; The idea of the UNPLUG algorithm is extended to solve the SPLC inDAGs, Form of the algorithm named Nettree for SPLC in Directed Acyclic Graphs(NSPLCDAG),the NNPLCUG and NSPLCDAG are transform the graph into a Nettree, then theconcept of the number of root paths of Nettree is used to solve the problem. Based onNSPLCDAG, a new algorithm named Nettree for the Longest Path in DAGs (NLPDAG) isconstructed which can find all the longest paths. Then NLPDAG is improved and the improvedNLPDAG can find one of the longest paths with linear time complexity.Final, the matrix multiplication to solve the path of length constraint mentioned in DiscreteMathematics is used to verify the correctness of algorithms, and test the efficiency of thealgorithm...