### Abstract

^{2}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 C

_{3}, C

_{4}, …, C|V| in G

^{2}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 | |

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 | United States |

City | New Orleans |

Period | 07/01/2018 → 10/01/2018 |

Series | Proceedings of the Twenty-ninth Annual Acm-siam Symposium |
---|

### Cite this

*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

}

*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.

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

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 -