Exploiting Sparsity for Bipartite Hamiltonicity
(2018) 29th International Symposium on Algorithms and Computation, ISAAC 2018p.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:
https://lup.lub.lu.se/record/967608a0-edb5-4dfb-b80b-d7c385a3e3a9
- author
- Björklund, Andreas LU
- organization
- publishing date
- 2018
- 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 >= 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}}, }