All reports by Author Hasan Abasi:

__
TR14-004
| 30th November 2013
__

Hasan Abasi, Nader Bshouty, Ariel Gabizon, Elad Haramaty#### On $r$-Simple $k$-Path

__
TR13-012
| 16th January 2013
__

Hasan Abasi, Nader Bshouty#### A Simple Algorithm for Undirected Hamiltonicity

Hasan Abasi, Nader Bshouty, Ariel Gabizon, Elad Haramaty

An $r$-simple $k$-path is a {path} in the graph of length $k$ that

passes through each vertex at most $r$ times. The \simpath{r}{k}

problem, given a graph $G$ as input, asks whether there exists an

$r$-simple $k$-path in $G$. We first show that this problem is

NP-Complete. We then show ...
more >>>

Hasan Abasi, Nader Bshouty

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 ... more >>>