scientific article; zbMATH DE number 1424546
Since any Steiner tree is an edge disjoint union of its full components, constructing full Steiner trees is of significant importance in the Steiner tree problem. Clearly, any algebraic approach of the Steiner tree problem involves a certain coordinate system. By Lemma 1.1, a coordinate system with three axes \(120^\circ\) apart, called a hexagonal coordinate system, is more natural than the common Cartesian coordinate system for constructing full Steiner trees. In Section 2 we study the use of hexagonal coordinates in the Steiner tree problem. Motivated also by Lemma 1.1, in Section 3 we define a generalization of Steiner trees, called APE-Steiner trees. Along the same line, the APE-Steiner tree problem can be solved using a general three coordinate system. In the last section, using hexagonal coordinate systems we give a direct proof of the NP-hardness of the Euclidean Steiner tree problem. For the entire collection see [Zbl 0932.00010].
- Hexagonal coordinate systems and Steiner minimal trees
- Euclidean Steiner trees optimal with respect to swapping 4-point subtrees
- THE UNIFORM ORIENTATION STEINER TREE PROBLEM IS NP-HARD
- scientific article; zbMATH DE number 3916324 (Why is no real title available?)
- scientific article; zbMATH DE number 3963856 (Why is no real title available?)
- scientific article; zbMATH DE number 1163726 (Why is no real title available?)
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4945795)
