Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2016.1
URN: urn:nbn:de:0030-drops-69485
URL: https://drops.dagstuhl.de/opus/volltexte/2017/6948/
Björklund, Andreas
Determinant Sums for Hamiltonicity (Invited Talk)
| pdf-format: |
|
Abstract
The best worst case guarantee algorithm to see if a graph has a Hamiltonian cycle, a closed tour visiting every vertex exactly once, for a long time was based on dynamic programming over all the vertex subsets of the graph. In this talk we will show some algebraic techniques that can be used to see if a graph has a Hamiltonian cycle much faster. These techniques utilize sums over determinants of matrices. In particular we will show how you can find out if an undirected graph has a Hamiltonian cycle much faster, but we will also talk about some partial results for the directed case and modular counting.
BibTeX - Entry
@InProceedings{bjrklund:LIPIcs:2017:6948,
author = {Andreas Bj{\"o}rklund},
title = {{Determinant Sums for Hamiltonicity (Invited Talk)}},
booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
pages = {1:1--1:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-023-1},
ISSN = {1868-8969},
year = {2017},
volume = {63},
editor = {Jiong Guo and Danny Hermelin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/6948},
URN = {urn:nbn:de:0030-drops-69485},
doi = {10.4230/LIPIcs.IPEC.2016.1},
annote = {Keywords: Hamiltonian cycle, exact algorithms, matrix determinant, algebraic techniques}
}
| Keywords: | Hamiltonian cycle, exact algorithms, matrix determinant, algebraic techniques | |
| Seminar: | 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) | |
| Issue date: | 2017 | |
| Date of publication: | 09.02.2017 |
