On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane R^2

DOI10.1007/S11590-020-01627-7MaRDI QIDQ828689zbMATH OpenOpenAlexWikidataFDO

Authors Jianping Li, Yujie Zheng, Junran Lichen, Wencheng Wang

Publication date 5 May 2021

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-020-01627-7

zbMATH Keywords

approximation algorithmsDelaunay triangulationSteiner pointsSteiner treea fixed line \(l\)

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Recommendations

• Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem
• \(1\)-line minimum rectilinear Steiner trees and related problems
• On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\)
• scientific article; zbMATH DE number 1796993
• Steiner Trees for Terminals Constrained to Curves

Cites work

• scientific article; zbMATH DE number 3485511 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• A constrained minimum spanning tree problem
• A faster circle-sweep Delaunay triangulation algorithm
• A good algorithm for smallest spanning trees with a degree constraint
• Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial optimization. Theory and algorithms
• Computational geometry. Algorithms and applications.
• Efficient algorithms for a family of matroid intersection problems
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Fibonacci heaps and their uses in improved network optimization algorithms
• Generalised \(k\)-Steiner tree problems in normed planes
• Introduction to algorithms.
• Optimal interconnection trees in the plane. Theory, algorithms and applications
• Steiner tree problems
• The 1-steiner tree problem
• Variations on the Euclidean Steiner tree problem and algorithms

Cited in

(8)

• Steiner tree problem with minimum number of Steiner points and bounded edge-length
• On the restricted \(k\)-Steiner tree problem
• Approximation algorithms for solving the 1-line minimum Steiner tree of line segments problem
• Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem
• On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\)
• On the number of minimal 1-Steiner trees
• Approximation algorithms for solving the line-capacitated minimum Steiner tree problem
• \(1\)-line minimum rectilinear Steiner trees and related problems

This page was built for publication: On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane \(\mathbb{R}^2\)

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