About DML-CZ | FAQ | Conditions of Use | Math Archives | Contact Us
  Previous |  Up |  Next

Article

Lamač, Jan ; Vlasák, Miloslav
Finding a Hamiltonian cycle using the Chebyshev polynomials. (English). In: Chleboun, J., Papež, J., Segeth, K., Šístek, J. and Vejchodský, T. (eds.): Programs and Algorithms of Numerical Mathematics. Proceedings of Seminar. Hejnice, June 23-28, 2024. , Prague, 2025. pp. 95-104
MSC: 65F08, 65M15, 65N15 | DOI: 10.21136/panm.2024.09
Keywords:
Hamiltonian cycle; Chebyshev polynomial; minimization of functional
Summary:
We present an algorithm of finding the Hamiltonian cycle in a general undirected graph by minimization of an appropriately chosen functional. This functional depends on the characteristic polynomial of the graph Laplacian matrix and attains its minimum at the characteristic polynomial of the Laplacian matrix of the Hamiltonian cycle.
Partner of
EuDML logo