The Complexity of Pebbling and Cover Pebbling
Watson, Nathaniel G.
Original · EN
This paper discusses the complexity of graph pebbling, dealing with both traditional pebbling and the recently introduced game of cover pebbling. Determining whether a configuration is solvable according to either the traditional definition or the cover pebbling definition is shown to be NP-complete. The problem of determining the cover pebbling number for an arbitrary demand configuration is shown to be NP-hard.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.