The Complexity of Graph Pebbling

DOI10.1137/050636218zbMath1123.05088arXivmath/0503698OpenAlexW2033611584MaRDI QIDQ5757392

Kevin G. Milans, Bryan K. Clark

Publication date: 6 September 2007

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0503698

zbMATH Keywords

complexitygraph pebbling\({\Pi_2^{\mathrm{p}}}\)-completeness

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (05C99)

Related Items (25)

Optimal pebbling on grids ⋮ Bounds on the rubbling and optimal rubbling numbers of graphs ⋮ Pebbling in 2-paths ⋮ Optimal pebbling number of the square grid ⋮ Modified linear programming and class 0 bounds for graph pebbling ⋮ The weight function lemma for graph pebbling ⋮ General graph pebbling ⋮ Graph pebbling algorithms and Lemke graphs ⋮ Optimal t-rubbling on complete graphs and paths ⋮ The optimal pebbling number of staircase graphs ⋮ Beyond NP: Quantifying over Answer Sets ⋮ Pebbling in powers of paths ⋮ Automating weight function generation in graph pebbling ⋮ Multi-color pebble motion on graphs ⋮ The complexity of pebbling reachability and solvability in planar and outerplanar graphs ⋮ Optimal pebbling number of graphs with given minimum degree ⋮ Restricted optimal pebbling and domination in graphs ⋮ Pebbling in semi-2-trees ⋮ Optimal pebbling and rubbling of graphs with given diameter ⋮ Computing bounds on product graph pebbling numbers ⋮ Graham's pebbling conjecture on products of many cycles ⋮ Threshold and complexity results for the cover pebbling game ⋮ Rubbling and optimal rubbling of graphs ⋮ A new lower bound on the optimal pebbling number of the grid ⋮ The optimal pebbling of spindle graphs

This page was built for publication: The Complexity of Graph Pebbling