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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

23 Citaten (Scopus)

Samenvatting

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.

Originele taal-2	Engels
Pagina's (van-tot)	246-250
Tijdschrift	Discrete Applied Mathematics
Volume	159
Nummer van het tijdschrift	4
DOI's	https://doi.org/10.1016/j.dam.2010.08.027
Status	Gepubliceerd - 2011

Toegang tot document

10.1016/j.dam.2010.08.027

Citeer dit

@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

Samenvatting

Toegang tot document

Vingerafdruk

Citeer dit