Hamiltonian index is NP-complete

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

doi:10.1016/j.dam.2010.08.027

Hamiltonian index is NP-complete

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

Research output: Contribution to journal › Article › Academic › peer-review

23 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 language	English
Pages (from-to)	246-250
Journal	Discrete Applied Mathematics
Volume	159
Issue number	4
DOIs	https://doi.org/10.1016/j.dam.2010.08.027
Publication status	Published - 2011

Access to Document

10.1016/j.dam.2010.08.027

Cite this

@article{7e716455fcd2477bb2c43ea288eab3b1,

title = "Hamiltonian index is NP-complete",

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.",

author = "Z. Ryjacek and G.J. Woeginger and L. Xiong",

year = "2011",

doi = "10.1016/j.dam.2010.08.027",

language = "English",

volume = "159",

pages = "246--250",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "4",

}

TY - JOUR

T1 - Hamiltonian index is NP-complete

AU - Ryjacek, Z.

AU - Woeginger, G.J.

AU - Xiong, L.

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

U2 - 10.1016/j.dam.2010.08.027

DO - 10.1016/j.dam.2010.08.027

M3 - Article

SN - 0166-218X

VL - 159

SP - 246

EP - 250

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 4

ER -

Hamiltonian index is NP-complete

Abstract

Access to Document

Fingerprint

Cite this