Hamiltonian index is NP-complete

Z. Ryjacek, G.J. Woeginger, L. Xiong

Research output: Contribution to journalArticleAcademicpeer-review

13 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)246-250
JournalDiscrete Applied Mathematics
Volume159
Issue number4
DOIs
Publication statusPublished - 2011

Fingerprint Dive into the research topics of 'Hamiltonian index is NP-complete'. Together they form a unique fingerprint.

  • Cite this