Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs
Pebble games are single-player games on DAGs involving placing and moving pebbles on nodes of the graph according to a certain set of rules. The goal is to pebble a set of target nodes using a minimum number of pebbles. In this paper, we present a possibly simpler proof of the result in [4] and stre...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Nature
2019
|
| Online Access: | https://hdl.handle.net/1721.1/121351 |