Inapproximability of the standard pebble game and hard to pebble graphs

DOI10.1007/978-3-319-62127-2_27zbMath1494.68192arXiv1707.06343OpenAlexW2963332897MaRDI QIDQ2405292

Erik D. Demaine, Quanquan C. Liu

Publication date: 22 September 2017

Full work available at URL: https://arxiv.org/abs/1707.06343

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (2)

Static-memory-hard functions, and modeling the cost of space vs. time ⋮ The red-blue pebble game on trees and DAGs with large input

This page was built for publication: Inapproximability of the standard pebble game and hard to pebble graphs