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

Publication: Research - peer-review › Article in proceedings – Annual report year: 2018

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 language | English |
---|---|

Title of host publication | Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms |

Publisher | SIAM - Society for Industrial and Applied Mathematics |

Publication date | 2018 |

Pages | 1645-1649 |

ISBN (electronic) | 978-1-61197-503-1 |

State | Published - 2018 |

Event | Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, United States |

### Conference

Conference | Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country | United States |

City | New Orleans |

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

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

Download as:

### Download statistics

No data available

ID: 142466093