A Type of Variation of Hamilton Path Problem with Applications
Jitian Xiao, Jun Wang · 2008
This paper describes a type of variation of the Hamilton path problem that can be applied to a type of applications. Unlike the original Hamilton path problem, the variation always has a solution. The problem of finding solutions to the variation of the Hamilton path problem is NP-complete. A heuristic for finding solutions to the problem is developed and analyzed. The heuristic is then applied to a real application scenario in the area of spatial cluster scheduling in spatial join processing. Experiments have demonstrated that the proposed method generates better cluster sequence than existing algorithms.