Get all the updates for this publication
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 | Data powered by TypesetJournal of Computer and System Sciences |
---|---|
Publisher | Data powered by TypesetElsevier BV |
Open Access | No |