A hamiltonian cycle in the square of a 2-connected graph in linear time

Stephen Alstrup, Agelos Georgakopoulos, Eva Rotenberg, Carsten Thomassen

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

133 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherSociety for Industrial and Applied Mathematics
Publication date2018
Pages1645-1649
ISBN (Electronic)978-1-61197-503-1
DOIs
Publication statusPublished - 2018
Event29th Annual ACM-SIAM Symposium on Discrete Algorithms - Astor Crowne Plaze, New Orleans French Quarter , New Orleans , United States
Duration: 7 Jan 201810 Jan 2018
Conference number: 29

Conference

Conference29th Annual ACM-SIAM Symposium on Discrete Algorithms
Number29
LocationAstor Crowne Plaze, New Orleans French Quarter
CountryUnited States
CityNew Orleans
Period07/01/201810/01/2018
SeriesProceedings of the Twenty-ninth Annual Acm-siam Symposium

Cite this

Alstrup, S., Georgakopoulos, A., Rotenberg, E., & Thomassen, C. (2018). A hamiltonian cycle in the square of a 2-connected graph in linear time. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1645-1649). Society for Industrial and Applied Mathematics. Proceedings of the Twenty-ninth Annual Acm-siam Symposium https://doi.org/10.1137/1.9781611975031.107
Alstrup, Stephen ; Georgakopoulos, Agelos ; Rotenberg, Eva ; Thomassen, Carsten. / A hamiltonian cycle in the square of a 2-connected graph in linear time. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2018. pp. 1645-1649 (Proceedings of the Twenty-ninth Annual Acm-siam Symposium).
@inproceedings{18f672b1ffb74abaa63ce55a447f3c99,
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 Agelos Georgakopoulos and Eva Rotenberg and Carsten Thomassen",
year = "2018",
doi = "10.1137/1.9781611975031.107",
language = "English",
pages = "1645--1649",
booktitle = "Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Society for Industrial and Applied Mathematics",

}

Alstrup, S, Georgakopoulos, A, Rotenberg, E & Thomassen, C 2018, A hamiltonian cycle in the square of a 2-connected graph in linear time. in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Proceedings of the Twenty-ninth Annual Acm-siam Symposium, pp. 1645-1649, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans , United States, 07/01/2018. https://doi.org/10.1137/1.9781611975031.107

A hamiltonian cycle in the square of a 2-connected graph in linear time. / Alstrup, Stephen; Georgakopoulos, Agelos; Rotenberg, Eva; Thomassen, Carsten.

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2018. p. 1645-1649 (Proceedings of the Twenty-ninth Annual Acm-siam Symposium).

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

TY - GEN

T1 - A hamiltonian cycle in the square of a 2-connected graph in linear time

AU - Alstrup, Stephen

AU - Georgakopoulos, Agelos

AU - Rotenberg, Eva

AU - Thomassen, Carsten

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

SP - 1645

EP - 1649

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

PB - Society for Industrial and Applied Mathematics

ER -

Alstrup S, Georgakopoulos A, Rotenberg E, Thomassen C. A hamiltonian cycle in the square of a 2-connected graph in linear time. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics. 2018. p. 1645-1649. (Proceedings of the Twenty-ninth Annual Acm-siam Symposium). https://doi.org/10.1137/1.9781611975031.107