Metraipolis › archive › dc_f4430d742e89

Dominator (graph theory) — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Dominator_(graph_theory)
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T14:28:32.833Z
SHA-256 of the archived text
b825a5f003d37169431b1162d52ce5a0c2a2eee5d6967e9d1c1eef57d3c9860f
Stable URL of this page
https://metraipolis.com/documento/dc_f4430d742e89

How to cite

Dominator (graph theory) — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Dominator_(graph_theory) (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_f4430d742e89 (Metraipolis archive dc_f4430d742e89, sha256 b825a5f003d37169431b1162d52ce5a0c2a2eee5d6967e9d1c1eef57d3c9860f)
BibTeX
@misc{dcf4430d742e89,
  title = {Dominator (graph theory) — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Dominator_(graph_theory)},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_f4430d742e89; sha256 b825a5f003d37169431b1162d52ce5a0c2a2eee5d6967e9d1c1eef57d3c9860f},
  year = {2026}
}

Archived text

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

In computer science, a node d of a control-flow graph dominates a node n if every path from the entry node to n must go through d. Notationally, this is written as d dom n (or sometimes d ≫ n). By definition, every node dominates itself. There are a number of related concepts: A node d strictly dominates a node n if d dominates n and d does not equal n. The immediate dominator or idom of a node n is the unique node that strictly dominates n but does not strictly dominate any other node that strictly dominates n. Every node reachable from the entry node has an immediate dominator (except the entry node). The dominance frontier of a node d is the set of all nodes ni such that d dominates an immediate predecessor of ni, but d does not strictly dominate ni. It is the set of nodes where d's dominance stops. A dominator tree is a tree where each node's children are those nodes it immediately dominates. The start node is the root of the tree.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «Dominator (graph theory)» — https://en.wikipedia.org/wiki/Dominator_(graph_theory)
Wikidata Q2589498 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q2589498
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Dominator_(graph_theory)?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 1369271865, consultata il 2026-10-07T14:08:00.543Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: ed2bcdf5285a47217375824bf7830de2d325f5ffdfc43e4af38c9ccbb7db8619