We present a CAT (Constant Amortized Time) algorithm for the exhaustive generation of the sand piles in the lattice SPM(n). More precisely, given an integer n, we show that the sequence of the sand piles in SPM(n) (ordered with respect to the negative lexicographic ordering) can be generated in O(1) amortized time by using O(n) space.
A Cat Algorithm for Sand Piles
MASSAZZA, PAOLO
2009-01-01
Abstract
We present a CAT (Constant Amortized Time) algorithm for the exhaustive generation of the sand piles in the lattice SPM(n). More precisely, given an integer n, we show that the sequence of the sand piles in SPM(n) (ordered with respect to the negative lexicographic ordering) can be generated in O(1) amortized time by using O(n) space.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
