The Fermat star of binary trees |
| |
Authors: | Fabrizio Luccio Linda Pagli |
| |
Affiliation: | Dipartimento di Informatica, Università di Pisa, Italy |
| |
Abstract: | A 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 δ?mn−3m, with a technique inherited from the studies on rotation distance. |
| |
Keywords: | Fermat point Fermat star Steiner tree Binary tree Rotation distance Combinatorial problems Design of algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|