Optimal Hamilton Path between Two Vertices in Halin Graph
Wen Xue · 2007
Finding the Hamilton path with minimum cost between two arbitrary given distinct vertices in a weighted graph,OHP for short,is a well known algorithm problem and has wide application in network routing and many as- pects of computer science.OHP is NP complete.Halin graph is a nontrivial generalization of tree and ring network. Effective algorithm to solve OHP in Halin graph is not found until now.This paper presents an effective algorithm to solve OHP problem in Halin graph by recursively shrinking fan structure.What’s more,the proof of correctness and the analysis of the complexity of the algorithm are also given.