Two Familiar Transitive Closure Algorithms Which Admit No Polynomial Time, Sublinear Space Implementations
- 1 February 1982
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 11 (1) , 130-137
- https://doi.org/10.1137/0211010
Abstract
No abstract availableKeywords
This publication has 15 references indexed in Scilit:
- Random walks, universal traversal sequences, and the complexity of maze problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- A note on time-space tradeoffs for computing continuous functionsInformation Processing Letters, 1979
- Upper and lower bounds on time-space tradeoffsPublished by Association for Computing Machinery (ACM) ,1979
- Two theorems on random polynomial timePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- Selection and sorting with limited storagePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- A pspace complete problem related to a pebble gamePublished by Springer Nature ,1978
- Time-space trade-offs in a pebble gameActa Informatica, 1978
- Shifting Graphs and Their ApplicationsJournal of the ACM, 1976
- The circuit value problem is log space complete for PACM SIGACT News, 1975
- An observation on time-storage trade offJournal of Computer and System Sciences, 1974