Geodesic
Asymptotic and exact results on the complexity of the Novelli-Pak-Stoyanovskii algorithm
Carsten Schneider1 ; Robin Sulzgruber2
1Research Institute for Symbolic Computation (RISC) Johannes Kepler University Linz 4040 Linz, Austria
2Fakultät fur Mathematik Universität Wien 1090 Wien, Austria
The electronic journal of combinatorics, Tome 24 (2017) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The Novelli-Pak-Stoyanovskii algorithm is a sorting algorithm for Young tableaux of a fixed shape that was originally devised to give a bijective proof of the hook-length formula. We obtain new asymptotic results on the average case and worst case complexity of this algorithm as the underlying shape tends to a fixed limit curve. Furthermore, using the summation package Sigma we prove an exact formula for the average case complexity when the underlying shape consists of only two rows. We thereby answer questions posed by Krattenthaler and Müller.
DOI : 10.37236/6354
Classification : 05E10, 33F10, 68W30
Mots-clés : Novelli-Pak-Stoyanovskii algorithm, standard Young tableau, hook-length formula, average case and worst case complexity, symbolic summation

Carsten Schneider  1   ; Robin Sulzgruber  2

1 Research Institute for Symbolic Computation (RISC) Johannes Kepler University Linz 4040 Linz, Austria
2 Fakultät fur Mathematik Universität Wien 1090 Wien, Austria 
@article{10_37236_6354,
     author = {Carsten Schneider and Robin Sulzgruber},
     title = {Asymptotic and exact results on the complexity of the {Novelli-Pak-Stoyanovskii} algorithm},
     journal = {The electronic journal of combinatorics},
     year = {2017},
     volume = {24},
     number = {2},
     doi = {10.37236/6354},
     zbl = {1366.05119},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/6354/}
}
TY  - JOUR
AU  - Carsten Schneider
AU  - Robin Sulzgruber
TI  - Asymptotic and exact results on the complexity of the Novelli-Pak-Stoyanovskii algorithm
JO  - The electronic journal of combinatorics
PY  - 2017
VL  - 24
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/6354/
DO  - 10.37236/6354
ID  - 10_37236_6354
ER  - 
%0 Journal Article
%A Carsten Schneider
%A Robin Sulzgruber
%T Asymptotic and exact results on the complexity of the Novelli-Pak-Stoyanovskii algorithm
%J The electronic journal of combinatorics
%D 2017
%V 24
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/6354/
%R 10.37236/6354
%F 10_37236_6354
Carsten Schneider; Robin Sulzgruber. Asymptotic and exact results on the complexity of the Novelli-Pak-Stoyanovskii algorithm. The electronic journal of combinatorics, Tome 24 (2017) no. 2. doi: 10.37236/6354

Cité par Sources :