1,721,062 research outputs found
Soluzione di ricorrenze nell'analisi di algoritmi
No full textSi presentano alcuni semplici teoremi per risolvere le relazioni di ricorrenza lineari, bilanciate e di ordine costante, che rappresentano il tempo di funzionamento dei piu' comuni algoritmi ricorsivi
The Fermat Star of Binary Trees
No full textA Fermat point P is one that minimizes the sum δ of the distances between P and the points of a given set. The resulting arrangement, called here a Fermat star, is a particular Steiner tree with only one intermediate point. We extend these concepts to rooted binary trees under the known rotation distance that measures the difference in shape of such trees. Minimizing δ is hard, due to the intrinsic difficulty of computing the rotation distance. Then we limit our study to establishing significant upper bounds for δ. In particular, for m binary trees of n vertices, we show how to construct efficiently a Fermat star with δ ≤ m n - 3 m, with a technique inherited from the studies on rotation distance
Lower Bounds on the Rotation Distance of Binary Trees
No full textThe rotation distance d(S, T) between two binary trees S, T of n vertices
is the minimum number of rotations to transform S into T. While it is known
that d(S, T) 2n − 6, a well known conjecture states that there are trees for
which this bound is sharp for any value of n 11. We are unable to prove the
conjecture, but we give here some simple criteria for lower bound evaluation,
leading for example to individuate some “regular” tree structures for which
d(S, T) = 3n/2 − O(1), or d(S, T) = 5n/3 − O(1).
Rotation distance, Lower bound, Binary tree, Design of algorithms
Chain Rotations: a New Look at Tree Distance
Full text linkAs well known the rotation distance D(S,T) between two binary trees S, T of n vertices is the minimum number of rotations of pairs of vertices to transform S into T. We introduce the new operation of chain rotation on a tree, involving two chains of vertices, that requires changing exactly three pointers in the data structure as for a standard rotation, and define the corresponding chain distance C(S,T). As for D(S,T), no polynomial time algorithm to compute C(S,T) is known. We prove a constructive upper bound and an analytical lower bound on C(S,T) based on the number of maximal chains in the two trees. More precisely we prove the general upper bound C(S,T)≤n-1 and we show that there are pairs of trees for which this bound is tight. No similar result is known for D(S,T) where the best upper and lower bounds are 2n-6 and 53n-4 respectively
- …
