.png){kind=icon}
.png){kind=icon}
Return
Beyond Quasi-Adjoint Graphs: On Polynomial-Time Solvable Cases of the Hamiltonian Cycle and Path Problems
.png){kind=icon}
PRE
AI
M
DOI：10.15388/24-INFOR568.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The Hamiltonian cycle and path problems are fundamental in graph theory and useful in modelling real-life problems. Research in this area is directed toward designing better and better algorithms for general problems, but also toward defining new special cases for which exact polynomial-time algorithms exist. In the paper, such new classes of digraphs are proposed. The classes include, among others, quasi-adjoint graphs, which are a superclass of adjoints, directed line graphs, and graphs modelling a DNA sequencing problem.
Keywords:
directed line graph
quasi-adjoint graph
Hamiltonian cycle
Hamiltonian path.
Journal
IF:
2.8
Papers:
402
Citations:
1.0K
Organization
Cited Papers