The complexity of pebbling in diameter two graphs

DOI10.1137/11084412XzbMATH Open1258.68066MaRDI QIDQ4899034FDOQ4899034

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)

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

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)

Cited In (11)

• The weight function lemma for graph pebbling
• Pebbling Algorithms in Diameter Two Graphs
• Restricted optimal pebbling is NP-hard
• The Complexity of Graph Pebbling
• Pebbling in 2-paths
• Two-player pebbling on diameter 2 graphs
• Graph pebbling algorithms and Lemke graphs
• Maximum pebbling number of graphs of diameter three
• Inapproximability of the standard pebble game and hard to pebble graphs
• Pebbling in semi-2-trees
• 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)