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

Stephen Alstrup; A Georgakopoulos; Eva Rotenberg; Carsten Thomassen

doi:10.1137/1.9781611975031.107

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

Stephen Alstrup, A Georgakopoulos, Eva Rotenberg, Carsten Thomassen

1 Citation (Scopus)

Abstract

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 |²) algorithm for producing cycles C3;C4; : : : ;C|V| in G2 of lengths 3; 4; : : : ; |V|, respectively.

Original language	English
Title of host publication	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Editors	Artur Czumaj
Publisher	Society for Industrial and Applied Mathematics
Publication date	2018
Pages	1645-1649
ISBN (Print)	978-161197503-1
DOIs	https://doi.org/10.1137/1.9781611975031.107
Publication status	Published - 2018
Event	29th Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, United States Duration: 7 Jan 2018 → 10 Jan 2018 Conference number: 29

Conference

Conference	29th Annual ACM-SIAM Symposium on Discrete Algorithms
Number	29
Country/Territory	United States
City	New Orleans
Period	07/01/2018 → 10/01/2018

Access to Document

10.1137/1.9781611975031.107

1.9781611975031.107Final published version, 478 KB

Cite this

A Hamiltonian Cycle in the Square of a 2-connected Graph in Linear Time. / Alstrup, Stephen; Georgakopoulos, A; Rotenberg, Eva et al.

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. ed. / Artur Czumaj. Society for Industrial and Applied Mathematics, 2018. p. 1645-1649.

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Alstrup, S, Georgakopoulos, A, Rotenberg, E & Thomassen, C 2018, A Hamiltonian Cycle in the Square of a 2-connected Graph in Linear Time. in A Czumaj (ed.), Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, pp. 1645-1649, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana, United States, 07/01/2018. https://doi.org/10.1137/1.9781611975031.107

@inproceedings{82677fdf99a64238bf0a7dab6cafbbac,

title = "A Hamiltonian Cycle in the Square of a 2-connected Graph in Linear Time",

abstract = "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.",

author = "Stephen Alstrup and A Georgakopoulos and Eva Rotenberg and Carsten Thomassen",

year = "2018",

doi = "10.1137/1.9781611975031.107",

language = "English",

isbn = "978-161197503-1",

pages = "1645--1649",

editor = "Czumaj, {Artur }",

booktitle = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Society for Industrial and Applied Mathematics",

address = "United States",

note = "29th Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 07-01-2018 Through 10-01-2018",

}

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 -

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

Abstract

Conference

Access to Document

Fingerprint

Cite this