LIPIcs.IPEC.2016.1.pdf
- Filesize: 200 kB
- 1 pages
Document
Determinant Sums for Hamiltonicity (Invited Talk)
Author
-
Part of:
Volume:
11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Parameterized and Exact Computation (IPEC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-02-09
Cite As Get BibTex
Andreas Björklund. Determinant Sums for Hamiltonicity (Invited Talk). In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.IPEC.2016.1
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.
Subject Classification
Keywords
- Hamiltonian cycle
- exact algorithms
- matrix determinant
- algebraic techniques
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads