Minimal Steiner trees for rectangular arrays of lattice points

DOI10.1006/JCTA.1996.2751MaRDI QIDQ1364229zbMATH OpenOpenAlexFDO

Authors M. Brazil, J. Hyam Rubinstein, D. A. Thomas, J. F. Weng, Nicholas Wormald

Publication date 5 February 1998

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcta.1996.2751

zbMATH Keywords

full components of a Steiner treelattice pointsminimal Steiner trees

Mathematics Subject Classification ID

Trees (05C05)

Review text

By distinction of several cases, the authors are able to construct a minimal Steiner tree for an arbitrary rectangular array of integer lattice points in the plane. For \(n\times n\)-arrays, this proves a conjecture by \textit{F. Chung}, \textit{M. Gardner} and \textit{R. Graham} [Math. Mag. 62, No. 2, 83-96 (1989; Zbl 0681.05018)] with the exception of the case \(n\equiv 0\bmod 6\), \(n>6\), where the authors were able to improve the conjecture. The proof rests on a theorem of another paper by the same authors [J. Comb. Theory, Ser. A 78, No. 1, 51-91 (1997; Zbl 0874.05018)], which characterizes the full components of a minimal Steiner tree for somewhat more general lattice sets. For non-square rectangular arrays, the proof is rather involved, but many drawings help to understand the constructions.

Recommendations

• Minimal Steiner trees for 2^ k 2^ k square lattices
• Full minimal Steiner trees on lattice sets
• Steiner minimal trees for regular polygons
• Steiner Trees on a Checkerboard
• Minimum rectilinear Steiner tree of n points in the unit square

Cites work

• Full minimal Steiner trees on lattice sets
• Minimal Steiner trees for 2^ k 2^ k square lattices
• Steiner Trees for Ladders
• Steiner Trees on a Checkerboard
• The Steiner tree problem

Cited in

(10)

• Full minimal Steiner trees on lattice sets
• Minimum rectilinear Steiner tree of n points in the unit square
• Minimal Steiner trees for 2^ k 2^ k square lattices
• On the structure and complexity of the 2-connected Steiner network problem in the plane
• On the restricted 1-Steiner tree problem
• On the restricted k-Steiner tree problem
• Approximating minimum Steiner point trees in Minkowski planes
• scientific article; zbMATH DE number 3922677 (Why is no real title available?)
• scientific article; zbMATH DE number 8006 (Why is no real title available?)
• Steiner minimal trees in small neighbourhoods of points in Riemannian manifolds

This page was built for publication: Minimal Steiner trees for rectangular arrays of lattice points

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