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)
Analysis of algorithms and problem complexity (68Q25) General topics in the theory of software (68N01)
Related Items
Multi-processor scheduling and expanders, Recursive construction for 3-regular expanders, Eigenvalues and expanders, Lower Bounds for the Size of Nondeterministic Circuits, On nontrivial separators for \(k\)-page graphs and simulations by nondeterministic one-tape Turing machines, Constructions of given-depth and optimal multirate rearrangeably nonblocking distributors, Time-space tradeoffs for computing functions, using connectivity properties of their circuits, Unnamed Item, Expander graphs and their applications, Small space analogues of Valiant's classes and the limitations of skew formulas, Superconcentrators of depth 2, Matrix rigidity, Trade-offs between communication and space, Reductions for monotone Boolean circuits, Highly symmetric expanders, Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory, On 3-pushdown graphs with large separators, A note on a construction of Margulis, A note on time-space tradeoffs for computing continuous functions, On Negations in Boolean Networks, Hamiltonian paths in Cayley graphs, Size-space tradeoffs for oblivious computations, The trade-off between the additive complexity and the asynchronicity of linear and bilinear algorithms, Diameters and Eigenvalues, OptORAMa: optimal oblivious RAM
Cites Work
