Fast möbius inversion in semimodular lattices and ER-labelable posets

Petteri Kaski, Jukka Kohonen, Thomas Westerbäck

Tutkimustuotos: LehtiartikkeliArticleScientificvertaisarvioitu

1 Sitaatiot (Scopus)

Abstrakti

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.

AlkuperäiskieliEnglanti
ArtikkeliP3.26
Sivut1-13
JulkaisuThe Electronic Journal of Combinatorics
Vuosikerta23
Numero3
TilaJulkaistu - 19 elokuuta 2016
OKM-julkaisutyyppiA1 Julkaistu artikkeli, soviteltu

Sormenjälki Sukella tutkimusaiheisiin 'Fast möbius inversion in semimodular lattices and ER-labelable posets'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

  • Siteeraa tätä