Abstract
We present a Monte Carlo algorithm that detects the presence of a Hamiltonian cycle in an n-vertex undirected bipartite graph of average degree delta >= 3 almost surely and with no false positives, in (2-2^{1-delta})^{n/2}poly(n) time using only polynomial space. With the exception of cubic graphs, this is faster than the best previously known algorithms. Our method is a combination of a variant of Björklund's 2^{n/2}poly(n) time Monte Carlo algorithm for Hamiltonicity detection in bipartite graphs, SICOMP 2014, and a simple fast solution listing algorithm for very sparse CNF-SAT formulas.
| Original language | English |
|---|---|
| Title of host publication | 29th International Symposium on Algorithms and Computation (ISAAC 2018) |
| Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| Pages | 3:1-3:11 |
| ISBN (Print) | 978-3-95977-094-1 |
| DOIs | |
| Publication status | Published - 2018 |
| Event | 29th International Symposium on Algorithms and Computation, ISAAC 2018 - Jiaoxi, Yilan, Taiwan Duration: 2018 Dec 16 → 2018 Dec 19 |
Conference
| Conference | 29th International Symposium on Algorithms and Computation, ISAAC 2018 |
|---|---|
| Country/Territory | Taiwan |
| City | Jiaoxi, Yilan |
| Period | 2018/12/16 → 2018/12/19 |
Subject classification (UKÄ)
- Computer Science
Free keywords
- Hamiltonian cycle
- bipartite graph