Two Familiar Transitive Closure Algorithms Which Admit No Polynomial Time, Sublinear Space Implementations
From MaRDI portal
Publication:3936198
DOI10.1137/0211010zbMath0478.68045OpenAlexW2064136209MaRDI QIDQ3936198
Publication date: 1982
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0211010
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Theory of software (68N99)
Related Items
Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity, Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits, The complexity of graph connectivity, Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS, Frameworks for designing in-place graph algorithms, A Framework for In-place Graph Algorithms, On Reducing the Space Requirements of a Straight-Line Algorithm, Two dynamic programming algorithms for which interpreted pebbling helps
