Two Familiar Transitive Closure Algorithms Which Admit No Polynomial Time, Sublinear Space Implementations

DOI10.1137/0211010zbMath0478.68045OpenAlexW2064136209MaRDI QIDQ3936198

Martin Tompa

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

zbMATH Keywords

sortingtime-space tradeoffBoolean matrixpebblingstraight-line program

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Theory of software (68N99)

Related Items (8)

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

This page was built for publication: Two Familiar Transitive Closure Algorithms Which Admit No Polynomial Time, Sublinear Space Implementations