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-7zbMATH Open1466.90116OpenAlexW3048039108WikidataQ114222159 ScholiaQ114222159MaRDI QIDQ828689FDOQ828689

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Introduction to algorithms.
• Title not available (Why is that?)
• Fibonacci heaps and their uses in improved network optimization algorithms
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computational geometry. Algorithms and applications.
• Title not available (Why is that?)
• Steiner tree problems
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• A good algorithm for smallest spanning trees with a degree constraint
• Efficient algorithms for a family of matroid intersection problems
• Generalised \(k\)-Steiner tree problems in normed planes
• A faster circle-sweep Delaunay triangulation algorithm
• Combinatorial optimization. Theory and algorithms
• Optimal interconnection trees in the plane. Theory, algorithms and applications
• A constrained minimum spanning tree problem
• Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem
• 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)