Hamiltonian index is NP-complete期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Hamiltonian index is NP-complete

Authors:	Zdeněk Ryjá?ek Gerhard J Woeginger

Institution:	^a Department of Mathematics, University of West Bohemia, P.O. Box 314, 306 14 Pilsen, Czech Republic ^b Institute of Theoretical Computer Science (ITI), Charles University, P.O. Box 314, 306 14 Pilsen, Czech Republic ^c Department of Math. and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB, Eindhoven, The Netherlands ^d Department of Mathematics, Beijing Institute of Technology, Beijing, 100081, PR China ^e Department of Mathematics, Qinghai University for Nationalities, PR China ^f Department of Mathematics, Jiangxi Normal University, PR China

Abstract:	In this paper we show that the problem to decide whether the hamiltonian index of a given graph is less than or equal to a given constant is NP-complete (although this was conjectured to be polynomial). Consequently, the corresponding problem to determine the hamiltonian index of a given graph is NP-hard. Finally, we show that some known upper and lower bounds on the hamiltonian index can be computed in polynomial time.

Keywords:	Complexity Hamiltonian index Line graph Branch-bond NP-complete problem
本文献已被 ScienceDirect 等数据库收录！