Geodesic
Geometry and complexity of O'Hara's algorithm
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) (2009).

Voir la notice de l'article provenant de la source Episciences

In this paper we analyze O'Hara's partition bijection. We present three type of results. First, we see that O'Hara's bijection can be viewed geometrically as a certain scissor congruence type result. Second, we present a number of new complexity bounds, proving that O'Hara's bijection is efficient in most cases and mildly exponential in general. Finally, we see that for identities with finite support, the map of the O'Hara's bijection can be computed in polynomial time, i.e. much more efficiently than by O'Hara's construction. 
@article{DMTCS_2009_special_256_a14,
     author = {Konvalinka, Matja\v{z} and Pak, Igor},
     title = {Geometry and complexity of {O'Hara's} algorithm},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)},
     year = {2009},
     doi = {10.46298/dmtcs.2692},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2692/}
}
TY  - JOUR
AU  - Konvalinka, Matjaž
AU  - Pak, Igor
TI  - Geometry and complexity of O'Hara's algorithm
JO  - Discrete mathematics & theoretical computer science
PY  - 2009
VL  - DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2692/
DO  - 10.46298/dmtcs.2692
LA  - en
ID  - DMTCS_2009_special_256_a14
ER  - 
%0 Journal Article
%A Konvalinka, Matjaž
%A Pak, Igor
%T Geometry and complexity of O'Hara's algorithm
%J Discrete mathematics & theoretical computer science
%D 2009
%V DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2692/
%R 10.46298/dmtcs.2692
%G en
%F DMTCS_2009_special_256_a14
Konvalinka, Matjaž; Pak, Igor. Geometry and complexity of O'Hara's algorithm. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) (2009). doi : 10.46298/dmtcs.2692. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2692/

Cité par Sources :