Document Type

Conference Proceeding

Publisher

IEEE Press

Faculty

Computing, Health and Science

School

Computer and Information Science

RAS ID

5954

Comments

This article was originally published as: Xiao, J. , & Wang, J. (2008). A Type of Variation of Hamilton Path Problem with Applications. Proceedings of 9th International Conference for Young Computer Scientists, 2008. ICYCS 2008. (pp. 88-93). Zhang Jia Jie, Hunan, China, . IEEE Press Conference Publishing Services CPS. Original article available here

© 2008 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Abstract

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.

DOI

10.1109/ICYCS.2008.470

Access Rights

free_to_read

 
COinS
 

Link to publisher version (DOI)

10.1109/ICYCS.2008.470