Metraipolis › archive › dc_11a3f85fa461
Cuthill–McKee algorithm — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Cuthill%E2%80%93McKee_algorithm
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-31T10:00:24.791Z
- SHA-256 of the archived text
65b645d3f25beccb9d02e9d0c5f834a0ec010c027b37990a104cb45b7f397c88- Stable URL of this page
https://metraipolis.com/documento/dc_11a3f85fa461
How to cite
Cuthill–McKee algorithm — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Cuthill%E2%80%93McKee_algorithm (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_11a3f85fa461 (Metraipolis archive dc_11a3f85fa461, sha256 65b645d3f25beccb9d02e9d0c5f834a0ec010c027b37990a104cb45b7f397c88)
BibTeX
@misc{dc11a3f85fa461,
title = {Cuthill–McKee algorithm — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Cuthill%E2%80%93McKee_algorithm},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_11a3f85fa461; sha256 65b645d3f25beccb9d02e9d0c5f834a0ec010c027b37990a104cb45b7f397c88},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Cuthill%E2%80%93McKee_algorithm. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In numerical linear algebra, the Cuthill–McKee algorithm (CM), named after Elizabeth Cuthill and James McKee, is an algorithm to permute a sparse matrix that has a symmetric sparsity pattern into a band matrix form with a small bandwidth. The reverse Cuthill–McKee algorithm (RCM) due to Alan George and Joseph Liu is the same algorithm but with the resulting index numbers reversed. In practice this generally results in less fill-in than the CM ordering when Gaussian elimination is applied. The Cuthill McKee algorithm is a variant of the standard breadth-first search algorithm used in graph algorithms. It starts with a peripheral node and then generates levels R i {\displaystyle R_{i}} for i = 1 , 2 , . . {\displaystyle i=1,2,..} until all nodes are exhausted. The set R i + 1 {\displaystyle R_{i+1}} is created from set R i {\displaystyle R_{i}} by listing all vertices adjacent to all nodes in R i {\displaystyle R_{i}} . These nodes are ordered according to predecessors and degree.
Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «linear algebra»).
Fonte: Wikipedia in inglese, voce «Cuthill–McKee algorithm» — https://en.wikipedia.org/wiki/Cuthill%E2%80%93McKee_algorithm
Wikidata Q1146458: «algorithm» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1146458
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Cuthill%E2%80%93McKee_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 1320572959, consultata il 2026-10-31T09:45:33.732Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 774c8a72ade197e2ac4a93c5573f8eebb616ba1b227a4ad75d62269673210b5e