REPORTS > KEYWORD > MATCHINGS:
Reports tagged with matchings:
TR00-049
| 2nd May 2000
Herbert Fleischner, Stefan Szeider
Herbert Fleischner, Stefan Szeider
Polynomial-Time Recognition of Minimal Unsatisfiable Formulas with Fixed Clause-Variable Difference
TR07-063
| 2nd July 2007
Tomas Feder, Carlos Subi
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
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 >>>