We consider the problem of fast zeta and Möbius transforms in finite posets, particularly in lattices. It has previously been shown that for a certain family of lattices, zeta and Möbius transforms can be computed in O(e) elementary arithmetic operations, where e denotes the size of the covering relation. We show that this family is exactly that of geometric lattices. We also extend the algorithms so that they work in e operations for all semimodular lattices, including chains and divisor lattices. Finally, for both transforms, we provide a more general algorithm that works in e operations for all ER-labelable posets.
|Julkaisu||The Electronic Journal of Combinatorics|
|Tila||Julkaistu - 19 elokuuta 2016|
|OKM-julkaisutyyppi||A1 Julkaistu artikkeli, soviteltu|