RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 1995 Volume 7, Issue 4, Pages 77–85 (Mi dm602)

This article is cited in 3 papers

New inequality relations between depth and delay

V. M. Khrapchenko


Abstract: We construct a sequence of minimal circuits $S_k$, $k=1,2,\ldots$, such that the delay $T(S_k)$ is considerably less than the depth $D(S_k)$, namely
$$ T(S_k)<\log_2D(S_k)+6. $$
It is shown that this result cannot be essentially improved.
This work is supported by Russian Foundation for Fundamental Investigations, Grant 93–011–1525.

UDC: 519.95

Received: 14.12.1993


 English version:
Discrete Mathematics and Applications, 1995, 5:6, 547–555

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024