Geodesic
Fast Möbius inversion in semimodular lattices and ER-labelable posets
The electronic journal of combinatorics, Tome 23 (2016) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/5998
Classification : 06C10, 06A07, 68W40, 68R05
Mots-clés : Möbius inversion, semimodular lattice, ER-labelable poset

Petteri Kaski  1   ; Jukka Kohonen  1   ; Thomas Westerbäck  1

1 Aalto University 
@article{10_37236_5998,
     author = {Petteri Kaski and Jukka Kohonen and Thomas Westerb\"ack},
     title = {Fast {M\"obius} inversion in semimodular lattices and {ER-labelable} posets},
     journal = {The electronic journal of combinatorics},
     year = {2016},
     volume = {23},
     number = {3},
     doi = {10.37236/5998},
     zbl = {1377.06006},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/5998/}
}
TY  - JOUR
AU  - Petteri Kaski
AU  - Jukka Kohonen
AU  - Thomas Westerbäck
TI  - Fast Möbius inversion in semimodular lattices and ER-labelable posets
JO  - The electronic journal of combinatorics
PY  - 2016
VL  - 23
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/5998/
DO  - 10.37236/5998
ID  - 10_37236_5998
ER  - 
%0 Journal Article
%A Petteri Kaski
%A Jukka Kohonen
%A Thomas Westerbäck
%T Fast Möbius inversion in semimodular lattices and ER-labelable posets
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/5998/
%R 10.37236/5998
%F 10_37236_5998
Petteri Kaski; Jukka Kohonen; Thomas Westerbäck. Fast Möbius inversion in semimodular lattices and ER-labelable posets. The electronic journal of combinatorics, Tome 23 (2016) no. 3. doi: 10.37236/5998

Cité par Sources :