文章基本信息

标题：Determinant Sums for Hamiltonicity (Invited Talk)
本地全文：下载
作者：Andreas Bj{\"o}rklund
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：63
页码：1:1-1:1
DOI：10.4230/LIPIcs.IPEC.2016.1
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Hamiltonian cycle; exact algorithms; matrix determinant; algebraic techniques