Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR13-012 | 16th January 2013 10:31

A Simple Algorithm for Undirected Hamiltonicity

RSS-Feed




TR13-012
Authors: Hasan Abasi, Nader Bshouty
Publication: 16th January 2013 11:39
Downloads: 4713
Keywords: 


Abstract:

We develop a new algebraic technique that gives a simple randomized algorithm for the simple $k$-path problem with the same complexity $O^*(1.657^k)$ as in [A. Bj\"orklund. Determinant Sums for Undirected Hamiltonicity. FOCS 2010, pp. 173--182, (2010). A. Bj\"orklund, T. Husfeldt, P. Kaski, M. Koivisto. Narrow sieves for parameterized paths and packings. {\it arXiv}:1007.1161v1, (2010).]



ISSN 1433-8092 | Imprint