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

Stephen Alstrup; Agelos 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
, Agelos Georgakopoulos
, Eva Rotenberg
, Carsten Thomassen

Department of Applied Mathematics and Computer Science

University of Copenhagen
University of Warwick

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

133 Downloads (Orbit)

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 G² of a 2-connected graph G = (V, E). The previous best was O(|V|²) 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 C₃, C₄, …, C|V| in G² of lengths 3,4, …, |V|, respectively.

Original language	English
Title of host publication	Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
Publisher	Society for Industrial and Applied Mathematics
Publication date	2018
Pages	1645-1649
ISBN (Electronic)	978-1-61197-503-1
DOIs	https://doi.org/10.1137/1.9781611975031.107
Publication status	Published - 2018
Event	29th Annual ACM-SIAM Symposium on Discrete Algorithms - Astor Crowne Plaze, New Orleans French Quarter , 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
Location	Astor Crowne Plaze, New Orleans French Quarter
Country/Territory	United States
City	New Orleans
Period	07/01/2018 → 10/01/2018
Sponsor	Association for Computing Machinery, Society for Industrial and Applied Mathematics

Access to Document

10.1137/1.9781611975031.107

OpenUrl availability

Check availability in DTU Findit

Cite this

@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",

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

}

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, 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

A hamiltonian cycle in the square of a 2-connected graph in linear time. / Alstrup, Stephen; Georgakopoulos, Agelos; Rotenberg, Eva et al.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2018. p. 1645-1649.

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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

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

SP - 1645

EP - 1649

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

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

OpenUrl availability

Fingerprint

Cite this