Hamiltonian index is NP-complete
From MaRDI portal
Publication:629366
DOI10.1016/j.dam.2010.08.027zbMath1210.05069OpenAlexW2059973876MaRDI QIDQ629366
Gerhard J. Woeginger, Zdeněk Ryjáček, Limning Xiong
Publication date: 9 March 2011
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2010.08.027
Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Even factors with a bounded number of components in iterated line graphs ⋮ On Computing the Hamiltonian Index of Graphs ⋮ Hamiltonian index of directed multigraph ⋮ Branch-bonds, two-factors in iterated line graphs and circuits in weighted graphs ⋮ Polynomially determining spanning connectivity of locally connected line graphs ⋮ Forbidden subgraphs on Hamiltonian index ⋮ Parameterized edge Hamiltonicity ⋮ Asymptotically sharpening the $s$-Hamiltonian index bound ⋮ Unnamed Item ⋮ Gray codes with bounded weights ⋮ Forbidden subgraphs for supereulerian and Hamiltonian graphs ⋮ On computing the Hamiltonian index of graphs ⋮ Unnamed Item ⋮ Panconnected index of graphs ⋮ Characterization of forbidden subgraphs for the existence of even factors in a graph ⋮ Minimum number of components of 2-factors in iterated line graphs ⋮ Degree sum conditions for Hamiltonian index ⋮ On the extended Clark-Wormold Hamiltonian-like index problem ⋮ On the dominating (induced) cycles of iterated line graphs
Cites Work
- The existence of even factors in iterated line graphs
- The Hamiltonian index of graphs
- The edge Hamiltonian path problem is NP-complete
- Hamiltonian iterated line graphs
- The Hamiltonian index of a graph and its branch-bonds
- On the 2-factor index of a graph
- The Planar Hamiltonian Circuit Problem is NP-Complete
- On Eulerian and Hamiltonian Graphs and Line Graphs
- On Hamiltonian Line-Graphs
- Unnamed Item
- Unnamed Item
