Conference paper
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
—
2018, pp. 1645-1649
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.
| Language: | English |
|---|---|
| Publisher: | Society for Industrial and Applied Mathematics |
| Year: | 2018 |
| Pages: | 1645-1649 |
| Proceedings: | 29th Annual ACM-SIAM Symposium on Discrete AlgorithmsACM-SIAM Symposium on Discrete Algorithms |
| ISBN: | 1611975034 and 9781611975031 |
| Types: | Conference paper |
| DOI: | 10.1137/1.9781611975031.107 |
| ORCIDs: | Thomassen, Carsten and 0000-0001-7896-8386 |
