On depth-reduction and grates
- 1 November 1983
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1 (02725428) , 323-328
- https://doi.org/10.1109/sfcs.1983.38
Abstract
For each ε(0 ≤ ε ≪ 1) a family Gn =(V(Gn), E(Gn)) of a cyclic digraphs can be constructively defined having the following properties: (a) #V(Gn) ≤ n · 2n+2 (b) degree (Gn) ≤ constant (c) it is necessary to remove Ω(n · 2n) edges in order to reduce the depth of Gn to (2n)ε. It is then shown: For suitable constants c1, C2 ≫ 0, there are (fn, n)- grates (see Definition 1) of size linear in n, where fn(x):= c1 · n2 x ≤ c2 ≤'; n/0 otherwiseKeywords
This publication has 9 references indexed in Scilit:
- A family of graphs with expensive depth-reductionPublished by Springer Nature ,2005
- On determinism versus non-determinism and related problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- On alternation IIActa Informatica, 1980
- Explicit constructions of linear size superconcentratorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- SuperconcentratorsSIAM Journal on Computing, 1977
- On Time Versus SpaceJournal of the ACM, 1977
- Graph-theoretic properties in computational complexityJournal of Computer and System Sciences, 1976
- On sparse graphs with dense long pathsComputers & Mathematics with Applications, 1975
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952