Abstract:
The problem of making bounded in-degree and out-degree data
structures partially persistent is considered. The node copying method of
Driscoll et al. is extended so that updates can be performed in
worst-case constant time on the pointer machine model. Previously it was
only known to be possible in amortised constant time [Driscoll89]. The result
is presented in terms of a new strategy for Dietz and Raman's dynamic two
player pebble game on graphs. It is shown how to implement the strategy and
the upper bound on the required number of pebbles is improved from
to d+2b, where b is the bound of the in-degree and
d the bound of the out-degree. We also give a lower bound that shows that
the number of pebbles depends on the out-degree d.
Available as PostScript, PDF.