The Complexity of Pebbling and Cover Pebbling

Publication date: 24 March 2005

Abstract: 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.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (05C99)

This page was built for publication: The Complexity of Pebbling and Cover Pebbling

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