A comparison of two variations of a pebble game on graphs

DOI10.1016/S0304-3975(81)80004-7MaRDI QIDQ1149448zbMATH OpenFDO

Authors Friedhelm Meyer auf der Heide

Publication date 1981

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(81)80004-7

zbMATH Keywords

Black Pebble GameBlack White Pebble Gamedirected acyclic graph

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Linear programming (90C05) Positional games (pursuit and evasion, etc.) (91A24)

Cites work

• An observation on time-storage trade off
• scientific article; zbMATH DE number 3643087 (Why is no real title available?)
• On Time Versus Space
• Space bounds for a game on graphs
• Storage requirements for deterministic polynomial time recognizable languages

Cited in

(9)

• Min Cut is NP-complete for edge weighted trees
• White pebbles help
• On the power of white pebbles
• Searching and pebbling
• Bandwidth and pebbling
• Reversible pebble games and the relation between tree-like and general resolution space
• An Application of Generalized Tree Pebbling to Sparse Matrix Factorization
• Pebble games and algebraic proof systems
• Pebble games and algebraic proof systems

This page was built for publication: A comparison of two variations of a pebble game on graphs

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