A note on bisecting minimum spanning trees
Authors:
Abstract
Let A be a finite set of points in a Euclidean space Er and M a minimum spanning tree (MST) for A, regarded as a subset of Er. If A′ ⊂ Er is a finite subset of M, then M is a spanning tree for A ∪ A′, but in general M will no longer be an MST. However, if A′ is chosen to be the set of all the midpoints of the line segments of M, then M will be an MST for A ∪ A′. Examples are given in which at least |A| ‐ 1 points must be adjoined to avoid destroying the MST.Keywords
This publication has 3 references indexed in Scilit:
- Steiner Minimal TreesSIAM Journal on Applied Mathematics, 1968
- Shortest Connection Networks And Some GeneralizationsBell System Technical Journal, 1957
- On the shortest spanning subtree of a graph and the traveling salesman problemProceedings of the American Mathematical Society, 1956