The Complexity of Pebbling and Cover Pebbling

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
20 pages, 3 figures

Keywords

Combinatorics, 05C99, 05C35, 68Q17

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/74612

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0503511
 http://arxiv.org/abs/math/0503511

Collections

arXiv