Pebbling meets coloring: Reversible pebble game on trees
作者：
Highlights：
• 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.
摘要
•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.
论文关键词：Pebbling games,Reversible pebbling,Edge-rank coloring,Combinatorics
论文评审过程：Received 29 November 2016, Revised 16 May 2017, Accepted 15 July 2017, Available online 4 September 2017, Version of Record 5 October 2017.
论文官网地址：https://doi.org/10.1016/j.jcss.2017.07.009
