Header menu link for other important links
Pebbling meets coloring: Reversible pebble game on trees
, Komarath Balagopal,
Published in Elsevier BV
Volume: 91
Pages: 33 - 41

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.

About the journal
JournalData powered by TypesetJournal of Computer and System Sciences
PublisherData powered by TypesetElsevier BV
Open AccessNo