Metraipolis › archive › dc_69f464089646
Fast factorization in diagram monoids — arXiv:2609.30804
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.30804
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T02:59:22.843Z
- SHA-256 of the archived text
c56aa7208ae647f0ec1cc27d91f7968857d618b8f84f95b21d23a811f4dd4094- Stable URL of this page
https://metraipolis.com/documento/dc_69f464089646
How to cite
Fast factorization in diagram monoids — arXiv:2609.30804 — arXiv (en), https://arxiv.org/abs/2609.30804 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_69f464089646 (Metraipolis archive dc_69f464089646, sha256 c56aa7208ae647f0ec1cc27d91f7968857d618b8f84f95b21d23a811f4dd4094)
BibTeX
@misc{dc69f464089646,
title = {Fast factorization in diagram monoids — arXiv:2609.30804},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.30804},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_69f464089646; sha256 c56aa7208ae647f0ec1cc27d91f7968857d618b8f84f95b21d23a811f4dd4094},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.30804. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We give explicit algorithms that factor elements of the standard diagram monoids into their usual generators. These algorithms generalize sorting from permutations to partial matchings and set partitions. In every case the worst-case complexity is $n^2$, which is optimal for algorithms that explicitly list the factors. We also determine the average complexity of our algorithms. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-28 in math.CO). Categorie arXiv: Rings and Algebras (math.RA) ; Data Structures and Algorithms (cs.DS); Combinatorics (math.CO). Pagina del lavoro: https://arxiv.org/abs/2609.30804 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-08T02:28:17.946Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).