The complexity of pebbling in diameter two graphs

DOI10.1137/11084412XMaRDI QIDQ4899034zbMATHFDO

Authors Charles A. Cusack, Timothy Lewis, Samuel Taggart, D. Simpson

Publication date 4 January 2013

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

zbMATH Keywords

NP-completegraph pebblingdiameter two

Mathematics Subject Classification ID

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

Recommendations

• The complexity of pebbling reachability and solvability in planar and outerplanar graphs
• Pebbling Algorithms in Diameter Two Graphs
• Maximum pebbling number of graphs of diameter three
• The Complexity of Graph Pebbling
• Graph pebbling algorithms and Lemke graphs

Cited in

(11)

• The weight function lemma for graph pebbling
• Two-player pebbling on diameter 2 graphs
• Restricted optimal pebbling is NP-hard
• Graph pebbling algorithms and Lemke graphs
• Maximum pebbling number of graphs of diameter three
• The Complexity of Graph Pebbling
• Pebbling in 2-paths
• Pebbling Algorithms in Diameter Two Graphs
• Pebbling in semi-2-trees
• Inapproximability of the standard pebble game and hard to pebble graphs
• The complexity of pebbling reachability and solvability in planar and outerplanar graphs

This page was built for publication: The complexity of pebbling in diameter two graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4899034)