Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Hasan Abasi:

TR14-004 | 30th November 2013
Hasan Abasi, Nader Bshouty, Ariel Gabizon, Elad Haramaty

On $r$-Simple $k$-Path

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

TR13-012 | 16th January 2013
Hasan Abasi, Nader Bshouty

A Simple Algorithm for Undirected Hamiltonicity

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

ISSN 1433-8092 | Imprint