Exploiting Sparsity for Bipartite Hamiltonicity

Andreas Björklund

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceedingPeer review

Sammanfattning

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.
Originalspråkengelska
Titel på värdpublikation29th International Symposium on Algorithms and Computation (ISAAC 2018)
FörlagSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Sidor3:1-3:11
ISBN (tryckt)978-3-95977-094-1
DOI
StatusPublished - 2018
Evenemang29th International Symposium on Algorithms and Computation, ISAAC 2018

- Jiaoxi, Yilan, Taiwan
Varaktighet: 2018 dec. 162018 dec. 19

Konferens

Konferens29th International Symposium on Algorithms and Computation, ISAAC 2018

Land/TerritoriumTaiwan
OrtJiaoxi, Yilan
Period2018/12/162018/12/19

Ämnesklassifikation (UKÄ)

  • Datavetenskap (datalogi)

Fingeravtryck

Utforska forskningsämnen för ”Exploiting Sparsity for Bipartite Hamiltonicity”. Tillsammans bildar de ett unikt fingeravtryck.

Citera det här