Minimum rectilinear Steiner tree of n points in the unit square

DOI10.1016/J.COMGEO.2017.06.007zbMATH Open1428.05053OpenAlexW2725261268MaRDI QIDQ1699296FDOQ1699296

Authors: Adrian Dumitrescu, Minghui Jiang 

Publication date: 19 February 2018

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2017.06.007

Recommendations

• Minimal Steiner trees for rectangular arrays of lattice points
• scientific article; zbMATH DE number 4041289
• A rectilinear steiner minimal tree algorithm for convex point sets
• Approximations for Steiner trees with minimum number of Steiner points
• Approximations for Steiner trees with minimum number of Steiner points
• A linear-time algorithm to construct a rectilinear Steiner minimal tree for \(k\)-extremal point sets
• Approximating minimum Steiner point trees in Minkowski planes
• Worst-case minimum rectilinear Steiner trees in all dimensions
• scientific article; zbMATH DE number 8006
• Minimizing path lengths in rectilinear Steiner minimum trees with fixed topology

zbMATH Keywords

coveringpackinginteger partitionminimum rectilinear Steiner tree

Mathematics Subject Classification ID

Trees (05C05)

Cites Work

• Title not available (Why is that?)
• A course in combinatorics.
• Geometric Spanner Networks
• Title not available (Why is that?)
• Steiner Minimal Trees
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Complexity of Computing Steiner Minimal Trees
• Lower bounds for rectilinear Steiner trees in bounded space
• On Steiner trees for bounded point sets
• The shortest path and the shortest road through n points
• How Long Can a Euclidean Traveling Salesman Tour Be?
• On Steiner Minimal Trees with Rectilinear Distance
• On Steiner’s Problem with Rectilinear Distance
• The largest minimal rectilinear steiner trees for a set of n points enclosed in a rectangle with given perimeter
• On the Shortest Path Through a Number of Points
• Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors
• Über einen geometrischen Satz
• Worst-case ratios of networks in the rectilinear plane
• Title not available (Why is that?)
• Fast heuristic algorithms for rectilinear Steiner trees
• Worst-case minimum rectilinear Steiner trees in all dimensions

Cited In (5)

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the stretch factor of polygonal chains
• Minimal Steiner trees for rectangular arrays of lattice points
• Title not available (Why is that?)

This page was built for publication: Minimum rectilinear Steiner tree of \(n\) points in the unit square

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