Metraipolis › archive › dc_05f080a6df5b
Algoritmo MST de tiempo lineal esperado — Wikipedia (es)
- Source
- Wikipedia (es)
- Original
- https://es.wikipedia.org/wiki/Algoritmo_MST_de_tiempo_lineal_esperado
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-17T06:38:50.643Z
- SHA-256 of the archived text
e939bb5b9ec3db2e3b42de2072c6b01555946d53f741817258b4651856da9a51- Stable URL of this page
https://metraipolis.com/documento/dc_05f080a6df5b
How to cite
Algoritmo MST de tiempo lineal esperado — Wikipedia (es) — Wikipedia (es), https://es.wikipedia.org/wiki/Algoritmo_MST_de_tiempo_lineal_esperado (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_05f080a6df5b (Metraipolis archive dc_05f080a6df5b, sha256 e939bb5b9ec3db2e3b42de2072c6b01555946d53f741817258b4651856da9a51)
BibTeX
@misc{dc05f080a6df5b,
title = {Algoritmo MST de tiempo lineal esperado — Wikipedia (es)},
howpublished = {Wikipedia (es)},
url = {https://es.wikipedia.org/wiki/Algoritmo_MST_de_tiempo_lineal_esperado},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_05f080a6df5b; sha256 e939bb5b9ec3db2e3b42de2072c6b01555946d53f741817258b4651856da9a51},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (es), https://es.wikipedia.org/wiki/Algoritmo_MST_de_tiempo_lineal_esperado. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
El algoritmo MST de tiempo lineal esperado (la abreviatura MST procede de la expresión inglesa "minimum spanning tree", "árbol recubridor mínimo" en español) es un algoritmo probabilista para calcular el árbol recubridor mínimo de un grafo ponderado sin vértices aislados. Fue desarrollado por David Karger, Philip Klein y Robert Tarjan. Se basa en técnicas relacionadas con el algoritmo de Borůvka, junto con un algoritmo para verificar un árbol de extensión mínima en tiempo lineal. Combina los paradigmas de diseño del algoritmo divide y vencerás, de un algoritmo voraz y de un algoritmo probabilista para lograr un rendimiento lineal esperado. Entre los algoritmos deterministas que encuentran el árbol de extensión mínima se incluyen el algoritmo de Prim, el algoritmo de Kruskal, el algoritmo de eliminación inversa y el algoritmo de Borůvka. Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in spagnolo, in ordine alfabetico). Fonte: Wikipedia in spagnolo, voce «Algoritmo MST de tiempo lineal esperado» — https://es.wikipedia.org/wiki/Algoritmo_MST_de_tiempo_lineal_esperado Wikidata Q5420845: «randomized algorithm for computing the minimum spanning forest of a weighted graph» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5420845 Autori: i contributori di Wikipedia (cronologia: https://es.wikipedia.org/wiki/Algoritmo_MST_de_tiempo_lineal_esperado?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 175347545, consultata il 2026-10-17T06:27:20.542Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 5e1d94a481aaf2311987abbd12d94d0d336a4d091679496c777cddcaa118752e