A NOTE ON THE HAMILTONIAN CIRCUIT PROBLEM ON DIRECTED PATH GRAPHS

作     者：NARASIMHAN, G 

作者机构：Comp. Sci. Dep. Univ. Wisconsin 1210 W. Dayton St. Madison WI 53706 USA 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：1989年第32卷第4期

页      面：167-170页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Hamiltonian circuit intersection graph undirected path graph directed path graph NP-completeness Hamiltonian path 

摘      要：Bertossi and Bonuccelli (1986) proved that the Hamiltonian Circuit Problem is NP-complete even when the inputs are restricted to the special class of undirected path graphs. The corresponding problem on directed path graphs was left as an open problem. We use a characterization of directed path graphs due to Monma and Wei (1986) to prove that the Hamiltonian Circuit Problem and the Hamiltonian Path Problem are NP-complete on directed path graphs.