Title
Beyond quasi-adjoint graphs: on polynomial-time solvable cases of the Hamiltonian cycle and path problems
Authors
[ 1 ] Instytut Informatyki, Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | [ P ] employee
Scientific discipline (Law 2.0)
Year of publication
2024
Published in
Article type
scientific article
Publication language
english
Keywords
EN
- directed line graph
- quasi-adjoint graph
- Hamiltonian cycle
- Hamiltonian path
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.
Date of online publication
18.09.2024
Pages (from - to)
807 - 816
License type
CC BY (attribution alone)
Open Access Mode
czasopismo hybrydowe
Open Access Text Version
final published version
Date of Open Access to the publication
at the time of publication
Ministry points / journal
100
System created by Poznań University of Technology
and Poznan Supercomputing and Networking Center
Log in through eKonto to add to SIS