1. Home
  2. To appear
  3. Beyond Quasi-Adjoint Graphs: On Polynomi ...

Informatica


Beyond Quasi-Adjoint Graphs: On Polynomial-Time Solvable Cases of the Hamiltonian Cycle and Path Problems
Pub. online: 18 September 2024      Type: Research Article      Open accessOpen Access
Received
1 September 2023
Accepted
1 September 2024
Published
18 September 2024

Abstract

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.

References

 
Bang-Jensen, J., Gutin, G. (1999). On the complexity of Hamiltonian path and cycle problems in certain classes of digraphs. Discrete Applied Mathematics, 95, 41–60.
 
Bang-Jensen, J., Gutin, G. (2002). Digraphs. Theory, Algorithms and Applications. Springer-Verlag, London.
 
Berge, C. (1973). Graphs and Hypergraphs. North-Holland Publishing Company, London.
 
Bertossi, A.A. (1981). The edge Hamiltonian path problem is NP-complete. Information Processing Letters, 13(4–5), 157–159.
 
Björklund, A. (2014). Determinant sums for undirected hamiltonicity. SIAM Journal on Computing, 43(1), 280–299.
 
Blazewicz, J., Kasprzak, M. (2006). Computational complexity of isothermic DNA sequencing by hybridization. Discrete Applied Mathematics, 154(5), 718–729.
 
Blazewicz, J., Kasprzak, M. (2012). Reduced-by-matching graphs: toward simplifying Hamiltonian circuit problem. Fundamenta Informaticae, 118(3), 225–244.
 
Blazewicz, J., Hertz, A., Kobler, D., de Werra, D. (1999). On some properties of DNA graphs. Discrete Applied Mathematics, 98(1–2), 1–19.
 
Blazewicz, J., Formanowicz, P., Kasprzak, M., Markiewicz, W.T. (2004). Sequencing by hybridization with isothermic oligonucleotide libraries. Discrete Applied Mathematics, 145(1), 40–51.
 
Blazewicz, J., Kasprzak, M., Leroy-Beaulieu, B., de Werra, D. (2008). Finding Hamiltonian circuits in quasi-adjoint graphs. Discrete Applied Mathematics, 156(13), 2573–2580.
 
Favaron, O., Ordaz, O. (1986). A sufficient condition for oriented graphs to be Hamiltonian. Discrete Mathematics, 58(3), 243–252.
 
Garey, M.R., Johnson, D.S. (1979). Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco.
 
Gould, R.J. (1991). Updating the Hamiltonian problem – a survey. Journal of Graph Theory, 15(2), 121–157.
 
Gross, J.L., Yellen, J., Zhang, P. (Eds.) (2013). Handbook of Graph Theory, second edition. Chapman and Hall/CRC, Boca Raton.
 
Jäger, G., Zhang, W. (2010). An effective algorithm for and phase transitions of the directed Hamiltonian cycle problem. Journal of Artificial Intelligence Research, 39, 663–687.
 
Kasprzak, M. (2018). Classification of de Bruijn-based labeled digraphs. Discrete Applied Mathematics, 234, 86–92.
 
Kasteleyn, P.W. (1963). A soluble self-avoiding walk problem. Physica, 29(12), 1329–1337.
 
Lawler, E.L. (1976). Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York.
 
Swat, S., Laskowski, A., Badura, J., Frohmberg, W., Wojciechowski, P., Swiercz, A., Kasprzak, M., Blazewicz, J. (2021). Genome-scale de novo assembly using ALGA. Bioinformatics, 37(12), 1644–1651.

Biographies

Kasprzak Marta
https://orcid.org/0000-0002-9863-5412
mkasprzak@cs.put.poznan.pl

M. Kasprzak is a professor at the Institute of Computing Science, Poznan University of Technology, Poland. She focuses her scientific research on bioinformatics, with a stress put on theoretical analysis of problems: combinatorial modelling of real-world problems, determining their computational complexity, designing algorithms. She published 73 articles and monographs, 43 of them indexed in Web of Science. She is a laureate of, among others, the Prime Minister Award for her doctoral dissertation, Award of the IV Division of Technical Sciences of the Polish Academy of Sciences in the field of computer science for her habilitation thesis, and the Medal of the National Education Commission.


Full article PDF XML
Full article PDF XML

Copyright
© 2024 Vilnius University
Open access article under the CC BY license.

Keywords
directed line graph quasi-adjoint graph Hamiltonian cycle Hamiltonian path

Metrics
since January 2020
129

Article info
views

 37

Full article
views
43

PDF
downloads

 16

XML
downloads


Share


RSS