An Approximation Algorithm for Finding the Longest Path in Undirected Connected Graph under Constrains
Hongming Cai · Jisuanji fangzhen · 2004
It is a NP-hard problem to find the longest path in an undirected connected graph, so people intend to find some approximation algorithms in practice, but all the existing algorithms are for a approximate longest path between two random vertexes in the graph. Based on that a longest path can not be inserted into a new vertex, we can insert all the nodes possible into the path between certain two vertexes in the DFSTraverseTree of the graph to get a path that cann't be inserted into again in a polynomial-time, usually this path will be a very good approximate longest path between two certain vertexes. The algorithm was used in the embroidery software, and the result shows that the algorithm can work well in practice.