Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Independent Sets:
TR01-047 | 3rd July 2001
Piotr Berman, Sridhar Hannenhalli, Marek Karpinski

1.375-Approximation Algorithm for Sorting by Reversals

Analysis of genomes evolving by inversions leads to a general
combinatorial problem of {\em Sorting by Reversals}, MIN-SBR, the problem of
sorting a permutation by a minimum number of reversals.
This combinatorial problem has a long history, and a number of other
motivations. It was studied in a great ... more >>>

TR20-109 | 19th July 2020
Oded Goldreich

On Testing Hamiltonicity in the Bounded Degree Graph Model

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