ArXiv.org · 2005 · 11 citations · 6 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationCombinatorial Game TheoryCombinatorial OptimizationComplexity TheoryComputational ComplexityGraph AlgorithmsTime ComplexityAlgorithmic Graph TheoryComputational Complexity Of Graph AlgorithmsGraph GamesNp-complete ProblemsNp-completenessPebble GamesPebbling GamesPolynomial Time Complexity
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.
6
Fan Chung · SIAM Journal on Discrete Mathematics · 1989 · 181 citations
Glenn Hurlbert · ArXiv.org · 2004 · 79 citations · Full text
The cover pebbling number of graphs
Betsy Crull, Tammy Cundiff, Paul M. Feltman et al. · Discrete Mathematics · 2005 · 58 citations
Conditions for Weighted Cover Pebbling of Graphs
Annalies Z. Vuong, M. Ian Wyckoff · ArXiv.org · 2004 · 15 citations · Full text