A CAT algorithm for the exhaustive generation of ice piles
Paolo Massazza; Roberto Radicioni
RAIRO - Theoretical Informatics and Applications (2011)
- Volume: 44, Issue: 4, page 525-543
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topMassazza, Paolo, and Radicioni, Roberto. "A CAT algorithm for the exhaustive generation of ice piles." RAIRO - Theoretical Informatics and Applications 44.4 (2011): 525-543. <http://eudml.org/doc/193074>.
@article{Massazza2011,
abstract = {
We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the
ice pile model$\mbox\{IPM\}_k$(n),
a generalization of the
sand pile model$\mbox\{SPM\}$(n).
More precisely, for any fixed integer k, we show that
the negative lexicographic ordering naturally identifies a tree structure on the lattice
$\mbox\{IPM\}_k$(n):
this lets us design an algorithm which generates all the ice piles of
$\mbox\{IPM\}_k$(n)
in amortized time
O(1)
and in space
O($\sqrt n$).
},
author = {Massazza, Paolo, Radicioni, Roberto},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Sand pile model; ice pile model; integer partitions;
exhaustive generation; CAT algorithms; discrete dynamical systems},
language = {eng},
month = {2},
number = {4},
pages = {525-543},
publisher = {EDP Sciences},
title = {A CAT algorithm for the exhaustive generation of ice piles},
url = {http://eudml.org/doc/193074},
volume = {44},
year = {2011},
}
TY - JOUR
AU - Massazza, Paolo
AU - Radicioni, Roberto
TI - A CAT algorithm for the exhaustive generation of ice piles
JO - RAIRO - Theoretical Informatics and Applications
DA - 2011/2//
PB - EDP Sciences
VL - 44
IS - 4
SP - 525
EP - 543
AB -
We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the
ice pile model$\mbox{IPM}_k$(n),
a generalization of the
sand pile model$\mbox{SPM}$(n).
More precisely, for any fixed integer k, we show that
the negative lexicographic ordering naturally identifies a tree structure on the lattice
$\mbox{IPM}_k$(n):
this lets us design an algorithm which generates all the ice piles of
$\mbox{IPM}_k$(n)
in amortized time
O(1)
and in space
O($\sqrt n$).
LA - eng
KW - Sand pile model; ice pile model; integer partitions;
exhaustive generation; CAT algorithms; discrete dynamical systems
UR - http://eudml.org/doc/193074
ER -
References
top- P. Bak, C. Tang and K. Wiesenfeld, Self-organized criticality. Phys. Rev. A38 (1988) 364–374.
- T. Brylawski, The lattice of integer partitions. Discrete Math. 6 (1973) 201–219.
- S. Corteel and D. Gouyou-Beauchamps, Enumeration of sand piles. Discrete Math. 256 (2002) 625–643.
- E. Duchi, R. Mantaci, H.D. Phan and D. Rossin, Bidimensional sand pile and ice pile models. PU.M.A. 17 (2007) 71–96.
- E. Goles and M.A. Kiwi, Games on line graphs and sand piles. Theoret. Comput. Sci. 115 (1993) 321–349.
- E. Goles, M. Morvan and H.D. Phan, Sandpiles and order structure of integer partitions. Discrete Appl. Math. 117 (2002) 51–64.
- M. Latapy, R. Mantaci, M. Morvan and H.D. Phan, Structure of same sand piles model. Theoret. Comput. Sci. 262 (2001) 525–556.
- P. Massazza, A CAT algorithm for sand piles. PU.M.A. 19 (2008) 147–158.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.