The Complexity of Pebbling and Cover Pebbling

Simple item page
dc.creatorWatson, Nathaniel G.
dc.date2005-03-24
dc.date2005-04-21
dc.date.accessioned2026-07-07T05:18:18Z
dc.date.available2026-07-07T05:18:18Z
dc.descriptionThis 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.
dc.description20 pages, 3 figures
dc.identifierhttps://arxiv.org/abs/math/0503511
dc.identifierhttp://arxiv.org/abs/math/0503511
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/74612
dc.subjectCombinatorics
dc.subject05C99, 05C35, 68Q17
dc.titleThe Complexity of Pebbling and Cover Pebbling
dc.typetext

Files

Collections

arXiv