• Pseudo Tree - a pseudo tree of an undirected graph 𝐆 = (𝐕, 𝐄) is a directed rooted tree 𝐓 = (𝐕, 𝐄’) if any arc in 𝐄 which is not in 𝐄’ is a back-arc in 𝐓 (i.e. it connects a node in 𝐓 to an ancestor in 𝐓). The arcs in 𝐄’ do not have to be in 𝐄
• Extended Graph - given a pseudo tree 𝐓 of 𝐆, the extended graph of 𝐆 relative to 𝐓 includes also the arcs in 𝐄’ that are not in 𝐄. That is, the extended graph is defined as 𝐆^𝐓 = (𝐕, 𝐄 ∪ 𝐄‘)

Examples

Subpages

maximum height pseudo tree is simply a chain, finding the minimum height pseudo tree however is NP-Complete. This problem is found in various tasks (e.g. finding the smallest possible OR Search Graph)

• Pseudo Tree - Minimal／Minimum (Height／Depth - Induced-Width - Tree-Width)