BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260921T212054Z
UID:Seminar-EcCo-1121@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20201014T130000
DTEND:20201014T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:Paul Spirakis: Computing second Hamiltonian cycles\n\nIn this work we consider the following total functional problem: Given a cubic Hamiltonian graph G and a Hamiltonian cycle C0 of G, how can we compute a second Hamiltonian cycle C1 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.2998n)) time and in linear space, thus improving the state of the art running time of O(2^(0.3n)) for solving this problem (among deterministic algorithms running in polynomial space).  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 C0 (where we may not have guarantees on the existence of a second Hamiltonian cycle), we provide a linear-time algorithm computing a second cycle of length n-4a(root(n)+2a)+8 where a=(D-2)/(d-2)  and D,d are the minimum and the maximum degree of the graph, respectively. This approximation result also improves the state of the art.\n\nAuthors: Argyrios Deligkas , George Mertzios, Paul Spirakis and  Viktor Zamaraev.\nAppeared in MFCS 2020\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1121
LOCATION:
END:VEVENT
END:VCALENDAR