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.IPEC.2016.1
URN: urn:nbn:de:0030-drops-69485
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6948/
Go to the corresponding LIPIcs Volume Portal

Björklund, Andreas

Determinant Sums for Hamiltonicity (Invited Talk)

pdf-format:
LIPIcs-IPEC-2016-1.pdf (0.2 MB)

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
Collection: 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Issue Date: 2017
Date of publication: 09.02.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI