Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Hamiltonicity:
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 >>>

TR20-109 | 19th July 2020
Oded Goldreich

On Testing Hamiltonicity in the Bounded Degree Graph Model

Revisions: 2

We show that testing Hamiltonicity in the bounded-degree graph model requires a linear number of queries. This refers to both the path and the cycle versions of the problem, and similar results hold also for the directed analogues.
In addition, we present an alternative proof for the known fact that ... more >>>

ISSN 1433-8092 | Imprint