Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Björklund, Andreas http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-69485
URL:

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: 2017


DROPS-Home | Fulltext Search | Imprint Published by LZI