The Complexity of Graph Pebbling

Simple item page
dc.creatorMilans, K.
dc.creatorClark, B.
dc.date2005-03-30
dc.date.accessioned2026-07-07T05:18:37Z
dc.date.available2026-07-07T05:18:37Z
dc.descriptionWe explore the complexity of computing the optimal pebbling number and pebbling number of a graph. We show that deciding whether the optimal pebbling number of G is at most k is NP-complete and deciding whether the pebbling number of G is at most k is Π_2-complete. Additionally, we provide a characterization of when an unordered set of pebbling moves can be ordered to form a valid sequence of pebbling moves.
dc.description24 pages, 6 figures
dc.identifierhttps://arxiv.org/abs/math/0503698
dc.identifierhttp://arxiv.org/abs/math/0503698
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/74724
dc.subjectCombinatorics
dc.subject05C99, 68Q17
dc.titleThe Complexity of Graph Pebbling
dc.typetext

Files

Collections

arXiv