کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951126 | 1441192 | 2018 | 9 صفحه PDF | دانلود رایگان |
- An exact characterization of reversible pebble number of rooted directed trees.
- A polynomial time algorithm to compute the reversible pebble game number of trees.
- Estimation of the number of steps needed to optimally pebble various tree families.
- Polynomial time pebbling of complete binary trees using almost optimal number of pebbles.
- Time-space trade-off for reversible pebbling for families of bounded degree trees.
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.
Journal: Journal of Computer and System Sciences - Volume 91, February 2018, Pages 33-41