Standard
A Hamiltonian Cycle in the Square of a 2-connected Graph in Linear Time. / Alstrup, Stephen; Georgakopoulos, A; Rotenberg, Eva; Thomassen, Carsten.
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
Harvard
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
APA
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 (pp. 1645-1649). Society for Industrial and Applied Mathematics.
https://doi.org/10.1137/1.9781611975031.107
Vancouver
Alstrup S, Georgakopoulos A, Rotenberg E, Thomassen C.
A Hamiltonian Cycle in the Square of a 2-connected Graph in Linear Time. In Czumaj A, editor, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics. 2018. p. 1645-1649
https://doi.org/10.1137/1.9781611975031.107
Author
Alstrup, Stephen ; Georgakopoulos, A ; Rotenberg, Eva ; Thomassen, Carsten. / A Hamiltonian Cycle in the Square of a 2-connected Graph in Linear Time. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. editor / Artur Czumaj. Society for Industrial and Applied Mathematics, 2018. pp. 1645-1649
Bibtex
@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. {\textcopyright} Copyright 2018 by SIAM.",
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 = "null ; Conference date: 07-01-2018 Through 10-01-2018",
}
RIS
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. © Copyright 2018 by SIAM.
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. © Copyright 2018 by SIAM.
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
Y2 - 7 January 2018 through 10 January 2018
ER -
