Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > HYPERCUBE:
Reports tagged with hypercube:
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 >>>


TR09-046 | 9th May 2009
Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff

Transitive-Closure Spanners of the Hypercube and the Hypergrid

Given a directed graph $G = (V,E)$ and an integer $k \geq 1$, a $k$-transitive-closure-spanner ($k$-TC-spanner) of $G$ is a directed graph $H = (V, E_H)$ that has (1) the same transitive-closure as $G$ and (2) diameter at most $k$. Transitive-closure spanners were introduced in \cite{tc-spanners-soda} as a common abstraction ... more >>>


TR10-048 | 24th March 2010
David GarcĂ­a Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet

Monotonicity Testing and Shortest-Path Routing on the Cube

We study the problem of monotonicity testing over the hypercube. As
previously observed in several works, a positive answer to a natural question about routing
properties of the hypercube network would imply the existence of efficient
monotonicity testers. In particular, if any $\ell$ disjoint source-sink pairs
on the directed hypercube ... more >>>


TR13-191 | 26th December 2013
Petr Savicky

Boolean functions with a vertex-transitive group of automorphisms

Revisions: 2 , Comments: 1

A Boolean function is called vertex-transitive, if the partition of the Boolean cube into the preimage of 0 and the preimage of 1 is invariant under a vertex-transitive group of isometric transformations of the Boolean cube. Several constructions of vertex-transitive functions and some of their properties are presented.

more >>>



ISSN 1433-8092 | Imprint