License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.3
URN: urn:nbn:de:0030-drops-99510
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9951/
Björklund, Andreas
Exploiting Sparsity for Bipartite Hamiltonicity
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.
BibTeX - Entry
@InProceedings{bjrklund:LIPIcs:2018:9951,
author = {Andreas Bj{\"o}rklund},
title = {{Exploiting Sparsity for Bipartite Hamiltonicity}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {3:1--3:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-094-1},
ISSN = {1868-8969},
year = {2018},
volume = {123},
editor = {Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9951},
URN = {urn:nbn:de:0030-drops-99510},
doi = {10.4230/LIPIcs.ISAAC.2018.3},
annote = {Keywords: Hamiltonian cycle, bipartite graph}
}
|
Keywords: |
|
Hamiltonian cycle, bipartite graph |
|
Collection: |
|
29th International Symposium on Algorithms and Computation (ISAAC 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
06.12.2018 |
