Metraipolis › archive › dc_28a9cf8ff54e

Expected linear time MST algorithm — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Expected_linear_time_MST_algorithm
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-15T19:29:32.310Z
SHA-256 of the archived text
b9db9c4c3c6f0476ca1dbce7d9d14bb9c78c7e90b125db046891accf9f84f0cd
Stable URL of this page
https://metraipolis.com/documento/dc_28a9cf8ff54e

How to cite

Expected linear time MST algorithm — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Expected_linear_time_MST_algorithm (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_28a9cf8ff54e (Metraipolis archive dc_28a9cf8ff54e, sha256 b9db9c4c3c6f0476ca1dbce7d9d14bb9c78c7e90b125db046891accf9f84f0cd)
BibTeX
@misc{dc28a9cf8ff54e,
  title = {Expected linear time MST algorithm — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Expected_linear_time_MST_algorithm},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_28a9cf8ff54e; sha256 b9db9c4c3c6f0476ca1dbce7d9d14bb9c78c7e90b125db046891accf9f84f0cd},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Expected_linear_time_MST_algorithm. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The expected linear time MST algorithm is a randomized algorithm for computing the minimum spanning forest of a weighted graph with no isolated vertices. It was developed by David Karger, Philip Klein, and Robert Tarjan. The algorithm relies on techniques from Borůvka's algorithm along with an algorithm for verifying a minimum spanning tree in linear time. It combines the design paradigms of divide and conquer algorithms, greedy algorithms, and randomized algorithms to achieve expected linear performance. Deterministic algorithms that find the minimum spanning tree include Prim's algorithm, Kruskal's algorithm, reverse-delete algorithm, and Borůvka's algorithm.

Tema degli esploratori: statistica e scienza dei dati (deposito sistematico; ricerca «algorithm»).
Fonte: Wikipedia in inglese, voce «Expected linear time MST algorithm» — https://en.wikipedia.org/wiki/Expected_linear_time_MST_algorithm
Wikidata Q5420845 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5420845
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Expected_linear_time_MST_algorithm?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 1237273602, consultata il 2026-10-15T18:35:04.489Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: ab1baaff2089a07e8aaa50d6bd0f25092fa8a2126852baaa4fbd5e6bda35274c