Graph-theoretic properties in computational complexity
From MaRDI portal
Publication:1236886
DOI10.1016/S0022-0000(76)80041-4zbMath0354.68071MaRDI QIDQ1236886
Publication date: 1976
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68N01: General topics in the theory of software
Related Items
Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory, Highly symmetric expanders, Reductions for monotone Boolean circuits, Size-space tradeoffs for oblivious computations, The trade-off between the additive complexity and the asynchronicity of linear and bilinear algorithms, Eigenvalues and expanders, On nontrivial separators for \(k\)-page graphs and simulations by nondeterministic one-tape Turing machines, Time-space tradeoffs for computing functions, using connectivity properties of their circuits, Superconcentrators of depth 2, Trade-offs between communication and space, A note on a construction of Margulis, A note on time-space tradeoffs for computing continuous functions, Multi-processor scheduling and expanders, Recursive construction for 3-regular expanders, Matrix rigidity, On 3-pushdown graphs with large separators, Expander graphs and their applications, Diameters and Eigenvalues
Cites Work
