Name
Title | ||
|---|---|---|
The complexity of pebbling reachability and solvability in planar and outerplanar graphs. |
Abstract | ||
|---|---|---|
Given a simple, connected graph, a pebbling configuration is a function from its vertex set to the nonnegative integers. A pebbling move between adjacent vertices removes two pebbles from one vertex and adds one pebble to the other. A vertex r is said to be reachable from a configuration if there exists a sequence of pebbling moves that places at least one pebble on r. A configuration is solvable if every vertex is reachable. We prove that determining reachability of a vertex and solvability of a configuration are NP-complete on planar graphs. We also prove that both reachability and solvability can be determined in O(n6) time on planar graphs with diameter two. Finally, for outerplanar graphs, we present a linear algorithm for determining reachability and a quadratic algorithm for determining solvability. To prove this result, we provide linear algorithms to determine all possible maximal configurations of pebbles that can be placed on the endpoints of a path and on two adjacent vertices in a cycle. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.dam.2014.03.008 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
Graph pebbling,Planar,Outerplanar,NP-complete | Journal | 172 |
ISSN | Citations | PageRank |
0166-218X | 2 | 0.41 |
References | Authors | |
13 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Timothy Lewis | 1 | 2 | 0.41 |
| Charles A. Cusack | 2 | 22 | 4.89 |
| Lisa Dion | 3 | 2 | 0.41 |