Improved Bounds on the Problem of Time-Space Trade-Off in the Pebble Game

DOI10.1145/322217.322233zbMath0468.05030OpenAlexW1965426100MaRDI QIDQ5904864

K. Ruediger Reischuk

Publication date: 1980

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322217.322233

zbMATH Keywords

directed acyclic graphstime-space trade-offpebble-game

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)

Related Items (1)

Extreme time-space tradeoffs for graphs with small space requirements

This page was built for publication: Improved Bounds on the Problem of Time-Space Trade-Off in the Pebble Game