The edge Hamiltonian path problem is NP-complete for bipartite graphs

DOI10.1016/0020-0190(93)90191-BzbMath0768.68158OpenAlexW2063001402MaRDI QIDQ1210313

Shu-Shang Wei, Ten-Hwang Lai

Publication date: 23 May 1993

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

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90191-b

zbMATH Keywords

computational complexitybipartite graphsedge graphNP- completeedge Hamiltonian path problem

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 (7)

Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete ⋮ On line graphs of subcubic triangle-free graphs ⋮ UNO is hard, even for a single player ⋮ Parameterized edge Hamiltonicity ⋮ Intersection graphs of non-crossing paths ⋮ Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks ⋮ Algorithms for maximum internal spanning tree problem for some graph classes

Cites Work

• The edge Hamiltonian path problem is NP-complete
• Parallel concepts in graph theory
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Use of graph-theoretic models for optimal relational database accesses to perform join

This page was built for publication: The edge Hamiltonian path problem is NP-complete for bipartite graphs