摘要：In this paper we consider the following total functional problem: Given a cubic Hamiltonian graph G and a Hamiltonian cycle Câ, of G, how can we compute a second Hamiltonian cycle Câ, â Câ, of G? Cedric Smith and William Tutte proved in 1946, using a non-constructive parity argument, that such a second Hamiltonian cycle always exists. Our main result is a deterministic algorithm which computes the second Hamiltonian cycle in O(nâ<.2^0.299862744n) = O(1.23103â¿) time and in linear space, thus improving the state of the art running time of O*(2^0.3n) = O(1.2312â¿) for solving this problem (among deterministic algorithms running in polynomial space). Whenever the input graph G does not contain any induced cycle Câ, on 6 vertices, the running time becomes O(nâ<. 2^0.2971925n) = O(1.22876â¿). Our algorithm is based on a fundamental structural property of Thomasonâs lollipop algorithm, which we prove here for the first time. In the direction of approximating the length of a second cycle in a (not necessarily cubic) Hamiltonian graph G with a given Hamiltonian cycle Câ, (where we may not have guarantees on the existence of a second Hamiltonian cycle), we provide a linear-time algorithm computing a second cycle with length at least n - 4α (â^Sn+2α)+8, where α = (Î"-2)/(δ-2) and δ,Î" are the minimum and the maximum degree of the graph, respectively. This approximation result also improves the state of the art.
