Name
Abstract | ||
|---|---|---|
We show that for any rooted directed tree T, its reversible pebble game number is always just one more than the edge rank coloring number of the underlying undirected tree U of T. It is known that given a DAG G as input, determining its reversible pebble game number is PSPACE-hard. Our result implies that the reversible pebble game number of trees can be computed in polynomial time. Using this connection as a tool, we also address several questions including that of finding the number of steps required to optimally pebble various families of trees. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.jcss.2017.07.009 | Journal of Computer and System Sciences |
Keywords | DocType | Volume |
Pebbling games,Reversible pebbling,Edge-rank coloring,Combinatorics | Journal | 91 |
ISSN | Citations | PageRank |
0022-0000 | 1 | 0.37 |
References | Authors | |
4 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Balagopal Komarath | 1 | 4 | 3.16 |
| Jayalal M. N. Sarma | 2 | 17 | 9.16 |
| Saurabh Sawlani | 3 | 7 | 5.17 |