Non-crossing of plane minimal spanning and minimal T1 networks

DOI10.1016/0012-365X(95)00071-4MaRDI QIDQ1377869zbMATH OpenOpenAlexWikidataFDO

Authors T. Cole

Publication date 12 May 1998

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(95)00071-4

zbMATH Keywords

minimal spanning treeshortest networksSteiner networksT1 networks

Mathematics Subject Classification ID

Trees (05C05)

Review text

The paper considers shortest networks spanning a finite set of points in the Euclidean plane. The problem to find a shortest network overall, usually called a minimal Steiner network, is NP-hard. On the other hand, to find a minimal spanning tree needs substantially less time. Other networks of interest are the T1 networks which are networks where the components consist of spanning edges, and Steiner networks with three given and one additional point (Steiner point). Computing a minimal T1 network is also a hard problem. The paper proves that a minimal T1 network and a minimal spanning network for the same set of points cannot cross (the same statement holds true for two distinct minimal spanning networks, which was shown by J. H. Rubinstein and D. A. Thomas).

Recommendations

• A.D. Alexandrov spaces with curvature bounded below
• scientific article; zbMATH DE number 176576
• scientific article; zbMATH DE number 1163706

Cites work

• A proof of the Gilbert-Pollak conjecture on the Steiner ratio
• A variational approach to the Steiner network problem
• On the Problem of Steiner
• Some remarks on the Steiner problem
• Steiner Minimal Trees
• The Complexity of Computing Steiner Minimal Trees

Cited in

(1)

• scientific article; zbMATH DE number 176576 (Why is no real title available?)

This page was built for publication: Non-crossing of plane minimal spanning and minimal T1 networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377869)