 1-line minimum rectilinear steiner trees and related problemsJianping Li (),
Junran Lichen (),
Wencheng Wang (),
Jean Yeh (),
YeongNan Yeh (),
Xingxing Yu () and
Yujie Zheng ()
Journal of Combinatorial Optimization, 2022, vol. 44, issue 4, No 35, 2832-2852 Abstract: Abstract In this paper, motivated by many practical applications, we address the 1-line minimum rectilinear Steiner tree (1L-MRStT) problem, which is a variation of the Euclidean minimum rectilinear Steiner tree problem. More specifically, given n points in the Euclidean plane $${\mathbb {R}}^2$$ R 2 , it is asked to find the location of a line l and a Steiner tree T(l), consisting only of vertical and horizontal line segments plus several successive segments located on this line l, to interconnect these n points and at least one point located on the line l, the objective is to minimize total weight of this Steiner tree T(l), i.e., $$\min \{\sum _{uv\in T(l)} w(u,v)$$ min { ∑ u v ∈ T ( l ) w ( u , v ) | T(l) is a Steiner tree mentioned-above $$\}$$ } , where we define a weight $$w(u,v)=0$$ w ( u , v ) = 0 if the two endpoints u and v of that edge $$uv \in T(l)$$ u v ∈ T ( l ) is located on the line l and otherwise we define a weight w(u, v) as the rectilinear distance between the two endpoints u and v of that edge $$uv \in T(l)$$ u v ∈ T ( l ) . Given a line l as an input in $${\mathbb {R}}^2$$ R 2 , we denote this problem as the 1-line-fixed minimum rectilinear Steiner tree (1LF-MRStT) problem; Furthermore, when the Steiner points of T(l) are all located on the fixed line l, we recall this problem as the 1-line-fixed-constrained minimum rectilinear Steiner tree (1LFC-MRStT) problem. We provide three following main contributions. (1) We design an algorithm $${{\mathcal {A}}}_{C}$$ A C to optimally solve the 1LFC-MRStT problem, where the algorithm $${{\mathcal {A}}}_{C}$$ A C runs in time $$O(n\log n)$$ O ( n log n ) ; (2) We prove that this algorithm $${{\mathcal {A}}}_{C}$$ A C is a 1.5-approximation algorithm to solve the 1LF-MRStT problem; (3) Combining the algorithm $${{\mathcal {A}}}_{C}$$ A C for many times and a key lemma proved by some techniques of computational geometry, we present a 1.5-approximation algorithm to solve the 1L-MRStT problem, where this algorithm runs in time $$O(n^3\log n)$$ O ( n 3 log n ) , and we finally provide another approximation algorithm to solve a special version of the 1L-MRStT problem, where that new algorithm runs in lower time $$O(n^2\log n)$$ O ( n 2 log n ) . Keywords: Combinatorial optimization; 1-line minimum rectilinear Steiner tree; 1-line-fixed-constrained minimum rectilinear Steiner tree; Approximation algorithms; Complexity (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:4:d:10.1007_s10878-021-00796-0 Ordering information: This journal article can be ordered from DOI: 10.1007/s10878-021-00796-0 Access Statistics for this article Journal of Combinatorial Optimization is currently edited by Thai, My T. More articles in Journal of Combinatorial Optimization from Springer |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.