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

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedings – Annual report year: 2018Researchpeer-review

View graph of relations

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
CitationsWeb of Science® Times Cited: No match on DOI

ID: 142466093