Episode 365
Dominator (graph theory)
Thu, 2018-May-03 01:34 UTC
Length - 2:16
Direct Link
Welcome to popular Wiki of the Day where we read the summary of a popular Wikipedia page every day.
With 234,352 views on Wednesday, 2 May 2018 our article of the day is Dominator (graph theory).
In computer science, in control flow graphs, a node d 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
≫
{\displaystyle \gg }
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, except the entry node, has an immediate dominator.
The dominance frontier of a node d is the set of all nodes n such that d dominates an immediate predecessor of n, but d does not strictly dominate n. 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. Because the immediate dominator is unique, it is a tree. The start node is the root of the tree.
This recording reflects the Wikipedia text as of 01:34 UTC on Thursday, 3 May 2018.
For the full current version of the article, go to http://en.wikipedia.org/wiki/Dominator_(graph_theory).
This podcast is produced by Abulsme Productions based on Wikipedia content and is released under a Creative Commons Attribution-ShareAlike License.
Visit wikioftheday.com for our archives, sister podcasts, and swag. Please subscribe to never miss an episode. You can also follow @WotDpod on Twitter.
Abulsme Productions produces the current events podcast Curmudgeon's Corner as well. Check it out in your podcast player of choice.
This has been Aditi. Thank you for listening to popular Wiki of the Day.
|
|
Buy WotD Stuff!!
