Reversible pebble game on trees

DOI10.1007/978-3-319-21398-9_7MaRDI QIDQ3196374zbMATH OpenOpenAlexFDO

Authors Balagopal Komarath, Jayalal Sarma M. N., Saurabh Sawlani

Publication date 29 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-21398-9_7

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Games on graphs (graph-theoretic aspects) (05C57)

Recommendations

• Pebbling meets coloring: reversible pebble game on trees
• Time and space complexity of reversible pebbling
• scientific article; zbMATH DE number 3976363
• scientific article; zbMATH DE number 2080928
• Rounds versus time for the two person pebble game

Cites work

• scientific article; zbMATH DE number 1303585 (Why is no real title available?)
• scientific article; zbMATH DE number 2080928 (Why is no real title available?)
• A polynomial algorithm for the min-cut linear arrangement of trees
• Complete Register Allocation Problems
• Separation of the monotone NC hierarchy
• Speedups of deterministic machines by synchronous parallel machines
• The PSPACE-Completeness of Black-White Pebbling
• The Pebbling Problem is Complete in Polynomial Space
• Time/Space Trade-Offs for Reversible Computation

Cited in

(9)

• Optimizing quantum space using spooky pebble games
• The Scholten/Dijkstra Pebble Game Played Straightly, Distributedly, Online and Reversed
• scientific article; zbMATH DE number 2080928 (Why is no real title available?)
• Nullstellensatz size-degree trade-offs from reversible pebbling
• Efficient pebbling for list traversal synopses with application to program rollback
• Nullstellensatz size-degree trade-offs from reversible pebbling
• Rounds versus time for the two person pebble game (extended abstract)
• Pebbling meets coloring: reversible pebble game on trees
• Rounds versus time for the two person pebble game

This page was built for publication: Reversible pebble game on trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3196374)