Experimental running times
The graphs in Fig. 3 show the running time for comparing worst case trees (see Fig. 2), (d-ary trees and random trees. There are six types of (d-ary trees; binary, 6-ary, 15-ary, and 30-ary and two types of random trees; r8s-based (see [12]) and trees with random topologies. The trees generated by r8s are binary, but by contracting edges, we can get trees of arbitrary degree (contracting an edge e connecting nodes u and v means removing u and e and attaching the rest of u's edges to v). Each edge is contracted with a probability that is inversely proportional with its length, i.e. a short edge has a higher probability of being contracted than a long edge. The trees with random topology are generated by adding leaves one by one, starting with a tree of size 2. A leaf can be added by attaching it to a random inner node or by spliting a random edge with a new node, to which the leaf is attached.
Figure 3  Experimental running times. The running time of the algorithm for worst case trees, d-ary trees and random trees. The lines plots the polynomials c. ni, where c is a fitted constant and i ∈ [1, 4]. The two bottommost plots are in log-scale on both the x- and y-axis. The running time for worst case input trees (as described in the previous section) is O(n3), because such trees have O(n) internal nodes and min{id, id'} is O(n). This is supported by the first graph in Fig. 3, which shows that the plot of the polynomial n3 (representing the best sum-of-squares fit of the polynomial c·n3 to the data-points) is closest to the plot of the running times with regard to slope.
The running time on the algorithm on d-ary trees is O(n2d MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaadaWcaaqaaiabd6gaUnaaCaaaleqabaGaeGOmaidaaaGcbaGaemizaqgaaaaa@309B@). The plots of the running times in the second graph are parallel, and one of them is plotted directly on top of a plot of the polynomial n2 (here c·n2 is fitted to the data-points for each d separately; the different colors match the d colors). This supports that they all have a running time of O(n2) for fixed d's. The graph also shows that higher degrees give lower running times, which is also expected. The reason why the algorithm is more than twice as fast on 6-ary trees than it is on binary trees, is that the number of internal nodes in 6-ary trees is less than in binary trees, and even though |V| is O(n) in both cases, that difference has an impact on the running time. The last graph shows the running time of the algorithm on trees created as either random trees (each topology is equally likely) or trees simulated using r8s (with edge contraction as described above). We have no theoretical running time for this data, but the graphs show that the running time is O(n2). Even though the plotted data is only a small random sample, this indicates that many pairs of trees actually have the property that min{id, id'} is O(dmin2 MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGKbazdaqhaaWcbaacbiGae8xBa0Mae8xAaKMae8NBa4gabaGaeGOmaidaaaaa@333E@). Therefore it is not unreasonable to expect that our algorithm runs in time O(n2) on trees used in practice. All experiments were performed on a standard PC (Pentium 4, 3 GHz, 1 Gb Ram) running Linux Fedora Core 3.