Skip to main content
Figure 5 | BMC Bioinformatics

Figure 5

From: Consensus properties for the deep coalescence problem and their application for scalable tree search

Figure 5

Running example for the proof of Theorem 1. A running example for the proof of Theorem 1 where T is a tree in the instance tuple I, S is an assumed solution for I , X = { a , b , c } , S ′ = S ( X ¯ ) , U = S x ′ , and R = Γ(S, X, w). Highlighted regions in T are the edge partitions E1, E2, and E3. The rest of edges form the partition E4. By counting the costs for each partition we have Σ1 =6 - 4 = 2, Σ2 =1 - 3 = −2, Σ3 = 2 − 1 = 1, and Σ4 =3 − 3 = 0. Overall we have DC(T, S) − DC(T, R) = 1.

Back to article page