A Hamiltonian Cycle in the Square of a 2-connected Graph in Linear Time

TY - GEN

T1 - A Hamiltonian Cycle in the Square of a 2-connected Graph in Linear Time

AU - Alstrup, Stephen

AU - Georgakopoulos, A

AU - Rotenberg, Eva

AU - Thomassen, Carsten

N1 - Conference code: 29

PY - 2018

Y1 - 2018

N2 - Fleischner's theorem says that the square of every 2-connected graph contains a Hamiltonian cycle. We present a proof resulting in an O(|E|) algorithm for producing a Hamiltonian cycle in the square G2 of a 2-connected graph G = (V;E). The previous best was O(|V |2) by Lau in 1980. More generally, we get an O(|E|) algorithm for producing a Hamiltonian path between any two prescribed vertices, and we get an O(|V |2) algorithm for producing cycles C3;C4; : : : ;C|V| in G2 of lengths 3; 4; : : : ; |V|, respectively.

AB - Fleischner's theorem says that the square of every 2-connected graph contains a Hamiltonian cycle. We present a proof resulting in an O(|E|) algorithm for producing a Hamiltonian cycle in the square G2 of a 2-connected graph G = (V;E). The previous best was O(|V |2) by Lau in 1980. More generally, we get an O(|E|) algorithm for producing a Hamiltonian path between any two prescribed vertices, and we get an O(|V |2) algorithm for producing cycles C3;C4; : : : ;C|V| in G2 of lengths 3; 4; : : : ; |V|, respectively.

U2 - 10.1137/1.9781611975031.107

DO - 10.1137/1.9781611975031.107

M3 - Article in proceedings

SN - 978-161197503-1

SP - 1645

EP - 1649

BT - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Czumaj, Artur

PB - Society for Industrial and Applied Mathematics

T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 7 January 2018 through 10 January 2018

ER -