The edge Hamiltonian path problem is NP-complete

DOI10.1016/0020-0190(81)90048-XzbMath0495.68058OpenAlexW2074710925MaRDI QIDQ1169818

Publication date: 1981

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(81)90048-x

zbMATH Keywords

NP-completeness cubic graph edge graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items

Thomassen's conjecture implies polynomiality of 1-Hamilton-connectedness in line graphs, On Computing the Hamiltonian Index of Graphs, Hamiltonian circuits in interval graph generalizations, Sequences of Radius k for Complete Bipartite Graphs, Deferred-query—An efficient approach for problems on interval and circular-arc graphs, Constrained shortest path tour problem: branch-and-price algorithm, Claw-free graphs---a survey, Unnamed Item, The constrained shortest path tour problem, On line graphs of subcubic triangle-free graphs, Hamiltonian paths in spanning subgraphs of line graphs, On Saito's conjecture and the Oberly-Sumner conjectures, UNO is hard, even for a single player, Parameterized edge Hamiltonicity, Classification of de Bruijn-based labeled digraphs, Constrained shortest path tour problem: models, valid inequalities, and Lagrangian heuristics, The constrained forward shortest path tour problem: Mathematical modeling and GRASP approximate solutions, Hamiltonian index is NP-complete, A lower bound on the Hamiltonian path completion number of a line graph, The multi-stripe travelling salesman problem, Meeting the Challenges of Optimized Memory Management in Embedded Vision Systems Using Operations Research, Gray codes with bounded weights, On computing the Hamiltonian index of graphs, Hamiltonian properties of locally connected graphs with bounded vertex degree, How many conjectures can you stand? A survey, On directed covering and domination problems, Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs, Local search algorithms for finding the Hamiltonian completion number of line graphs, Hydras: directed hypergraphs and Horn formulas, Contracting to a longest path in H-free graphs, Finding Hamiltonian circuits in quasi-adjoint graphs, Sequences of radius \(k\) for complete bipartite graphs, The edge Hamiltonian path problem is NP-complete for bipartite graphs, Toughness in graphs -- a survey, Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs, A linear time recognition algorithm for proper interval graphs, Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks, Jump number maximization for proper interval graphs and series-parallel graphs, Finding Hamiltonian cycles in \(\{\)quasi-claw, \(K_{1,5},K_{1,5} + e\}\)-free graphs with bounded Dilworth numbers, Forbidden subgraphs, hamiltonicity and closure in claw-free graphs, Finding Hamiltonian circuits in proper interval graphs, Combinatorial analysis (nonnegative matrices, algorithmic problems), Minimum Dominating Trail Set for Two-Terminal Series Parallel Graphs, On Directed Covering and Domination Problems, Forbidden subgraphs for existences of (connected) 2-factors of a graph, Finding Hamiltonian circuits in interval graphs, A linear algorithm for the Hamiltonian completion number of the line graph of a tree

Cites Work