The complexity of pebbling reachability and solvability in planar and outerplanar graphs

DOI10.1016/j.dam.2014.03.008zbMath1288.05225OpenAlexW1968346761MaRDI QIDQ2449128

Lisa Dion, Timothy Lewis, Charles A. Cusack

Publication date: 6 May 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.03.008

zbMATH Keywords

outerplanarNP-completegraph pebbling

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Pebbling in 2-paths, The weight function lemma for graph pebbling, Graph pebbling algorithms and Lemke graphs, Pebbling in semi-2-trees

Cites Work

• Unnamed Item
• Unnamed Item
• \(t\)-pebbling and extensions
• General graph pebbling
• Characterizations of outerplanar graphs
• A Graph Pebbling Algorithm on Weighted Graphs
• Pebbling Algorithms in Diameter Two Graphs
• Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
• An Efficient Cycle Vector Space Algorithm for Listing All Cycles of a Planar Graph
• Minimum dominating cycles in outerplanar graphs
• Planar Formulae and Their Uses
• Pebbling in diameter two graphs and products of paths
• Domination in planar graphs with small diameter*
• The Complexity of Pebbling in Diameter Two Graphs
• Weighted pebbling numbers on graphs
• The Complexity of Graph Pebbling