Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MATCHINGS:
Reports tagged with matchings:

TR07-063 | 2nd July 2007
Tomas Feder, Carlos Subi

#### Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations

We conjecture that for every perfect matching $M$ of the $d$-dimensional
$n$-vertex hypercube, $d\geq 2$, there exists a second perfect matching $M'$
such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the
$d$-dimensional hypercube. We prove this conjecture in the case where there are
two dimensions ... more >>>

TR08-087 | 31st July 2008
Tomas Feder, Carlos Subi

#### Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations (revised)

It has been shown that for every perfect matching $M$ of the $d$-dimensional
$n$-vertex hypercube, $d\geq 2, n=2^d$, there exists a second perfect matching
$M'$ such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the
$d$-dimensional hypercube. We prove a generalization of a special case of ... more >>>

TR14-065 | 2nd May 2014
Andrzej Dudek , Marek Karpinski, Andrzej Rucinski, Edyta Szymanska

#### Approximate Counting of Matchings in $(3,3)$-Hypergraphs

We design a fully polynomial time approximation scheme (FPTAS) for counting the number of matchings (packings) in arbitrary 3-uniform hypergraphs of maximum degree three, referred to as $(3,3)$-hypergraphs. It is the first polynomial time approximation scheme for that problem, which includes also, as a special case, the 3D Matching counting ... more >>>

TR14-146 | 6th November 2014
Ilario Bonacina, Nicola Galesi, Tony Huynh, Paul Wollan

#### Space proof complexity for random $3$-CNFs via a $(2-\epsilon)$-Hall's Theorem

We investigate the space complexity of refuting $3$-CNFs in Resolution and algebraic systems. No lower bound for refuting any family of $3$-CNFs was previously known for the total space in resolution or for the monomial space in algebraic systems. We prove that every Polynomial Calculus with Resolution refutation of a ... more >>>

ISSN 1433-8092 | Imprint