1,721,111 research outputs found
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
Brief Announcement: Distributed Swap Edges computation for Minimum Cost Spanning Trees
No full textGiven a weighted graph G(VG, EG) representing a communication network, with n nodes and m edges where the weights are positive integers, its Spanning Tree is typically used to route messages. In [1] the routing cost of a spanning tree is defined as the sum of the distances over all pairs of vertices of this tree. Hence, the most suitable spanning tree for the routing problem is the one minimizing the routing cost: the Minimum Routing Cost Spanning Tree (MRCST)
- …
