DIMACS TR: 98-02
On the Complexity of Generation in Ternary Hamming Spaces
Authors: Endre Boros, Peter L. Hammer, Frederica Ricca and Bruno Simeone
ABSTRACT
In this paper, a follow-up of DIMACS Report 98-01,
we continue to study ternary Hamming spaces $\TT^n$,
where $\TT=\{0,1,2\}$, and their generators.
In particular, we are interested in the computational complexity of the
generation
of all vectors with respect to a specific generator $G\subseteq \TT^n$.
We consider several parameters, i.e., depth and load, which provide
alternative ways
to measure the computational effort required in order to generate all points
of $\TT^n$
starting from those of $G$.
We establish lower and upper bounds on the minimum depth and the minimum
load for a generator in,
and prove that some of them are sharp.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-02.ps.gz
DIMACS Home Page