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

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2018

Documents

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 <i>O</i>(|<i>E</i>|) algorithm for producing a Hamiltonian cycle in the square <i>G</i><sup>2</sup> of a 2-connected graph <i>G</i> = (<i>V, E</i>). The previous best was <i>O</i>(|<i>V</i>|<sup>2</sup>) by Lau in 1980. More generally, we get an <i>O</i>(|<i>E</i>|) algorithm for producing a Hamiltonian path between any two prescribed vertices, and we get an <i>O</i>(|<i>V</i>|<sup>2</sup>) algorithm for producing cycles <i>C</i><sub>3</sub>, <i>C</i><sub>4</sub>, . . . , <i>C</i><sub>|V|</sub> in <i>G</i><sub>2</sub> of lengths 3, 4, . . . , |<i>V</i>|, respectively.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherSIAM - Society for Industrial and Applied Mathematics
Publication date2018
Pages1645-1649
ISBN (electronic)978-1-61197-503-1
StatePublished - 2018
Event29th Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans , United States

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
Download as:
Download as PDF
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
Word

Download statistics

No data available

ID: 142466093