Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Exploiting Sparsity for Bipartite Hamiltonicity

Björklund, Andreas LU (2018) 29th International Symposium on Algorithms and Computation, ISAAC 2018

 p.1-11
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.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Hamiltonian cycle, bipartite graph
host publication
29th International Symposium on Algorithms and Computation (ISAAC 2018)
pages
1 - 11
publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
conference name
29th International Symposium on Algorithms and Computation, ISAAC 2018<br/><br/>
conference location
Jiaoxi, Yilan, Taiwan
conference dates
2018-12-16 - 2018-12-19
external identifiers
  • scopus:85063677034
ISBN
978-3-95977-094-1
DOI
10.4230/LIPIcs.ISAAC.2018.3
language
English
LU publication?
yes
id
967608a0-edb5-4dfb-b80b-d7c385a3e3a9
date added to LUP
2019-02-01 08:31:40
date last changed
2022-03-17 21:09:53
@inproceedings{967608a0-edb5-4dfb-b80b-d7c385a3e3a9,
  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 &gt;= 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.}},
  author       = {{Björklund, Andreas}},
  booktitle    = {{29th International Symposium on Algorithms and Computation  (ISAAC 2018)}},
  isbn         = {{978-3-95977-094-1}},
  keywords     = {{Hamiltonian cycle; bipartite graph}},
  language     = {{eng}},
  pages        = {{1--11}},
  publisher    = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
  title        = {{Exploiting Sparsity for Bipartite Hamiltonicity}},
  url          = {{http://dx.doi.org/10.4230/LIPIcs.ISAAC.2018.3}},
  doi          = {{10.4230/LIPIcs.ISAAC.2018.3}},
  year         = {{2018}},
}