CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishA 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.
| Autori interni: | ||
| Autori: | LUCCIO F; PAGLI L | |
| Titolo: | The Fermat Star of Binary Trees | |
| Anno del prodotto: | 2009 | |
| Digital Object Identifier (DOI): | 10.1016/j.ipl.2009.02.001 | |
| Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
http://hdl.handle.net/11568/197459
Copyright © 2021