Title :
Extended Hamilton Circuit and Its Application
Author_Institution :
Dept. of Basic Educ., Zhejiang Water Conservancy & Hydropower Coll., Hangzhou, China
Abstract :
In this paper, we propose the definition of extended Hamilton circuit (EHC) and its corresponding optimization version of Extended Hamilton Circuit Problem (OEHCP), as well as prove OEHCP to be NP-hard and design an efficient heuristic for OEHCP. In addition, we study an interesting Hierarchical Touring Problem (HTP), and develop a heuristic for HTP on basis of the heuristic for OEHCP.
Keywords :
computational complexity; graph theory; optimisation; NP-hard problem; extended Hamilton circuit problem; hierarchical touring problem; optimization; Airplanes; Circuits; Cities and towns; Costs; Design optimization; Educational institutions; Hydroelectric power generation; Postal services; Sufficient conditions; Water conservation; Extended Hamilton circuit; Hierarchical Touring;
Conference_Titel :
Information and Computing (ICIC), 2010 Third International Conference on
Conference_Location :
Wuxi, Jiang Su
Print_ISBN :
978-1-4244-7081-5
Electronic_ISBN :
978-1-4244-7082-2
DOI :
10.1109/ICIC.2010.199
