The Library
A Hamiltonian cycle in the square of a 2-connected graph in linear time
Tools
Alstrup, Stephen, Georgakopoulos, Agelos, Rotenberg, Eva and Thomassen, Carsten (2018) A Hamiltonian cycle in the square of a 2-connected graph in linear time. In: Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, USA, 7-10 Jan 2018 pp. 1645-1649. doi:10.1137/1.9781611975031.107
|
PDF
WRAP-Hamiltonian-cycle-square-2-connected-graph-Georgakopoulos-2018.pdf - Accepted Version - Requires a PDF viewer. Download (813Kb) | Preview |
Official URL: http://dx.doi.org/10.1137/1.9781611975031.107
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.
Item Type: | Conference Item (Paper) | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
|||||||||||||||
Library of Congress Subject Headings (LCSH): | Graph algorithms | |||||||||||||||
Book Title: | Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms | |||||||||||||||
Official Date: | 2018 | |||||||||||||||
Dates: |
|
|||||||||||||||
Page Range: | pp. 1645-1649 | |||||||||||||||
DOI: | 10.1137/1.9781611975031.107 | |||||||||||||||
Status: | Peer Reviewed | |||||||||||||||
Publication Status: | Published | |||||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | |||||||||||||||
Date of first compliant deposit: | 8 May 2018 | |||||||||||||||
Date of first compliant Open Access: | 8 May 2018 | |||||||||||||||
RIOXX Funder/Project Grant: |
|
|||||||||||||||
Conference Paper Type: | Paper | |||||||||||||||
Title of Event: | Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms | |||||||||||||||
Type of Event: | Conference | |||||||||||||||
Location of Event: | New Orleans, USA | |||||||||||||||
Date(s) of Event: | 7-10 Jan 2018 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year