Approximating Steiner trees and forests with minimum number of Steiner points
作者：
Highlights：
• We consider connectivity problems on unit-disc graphs in a convex metric space.
• Let Δ be the maximum number of independent points in a unit ball.
• For Steiner Tree with Minimum Number of Steiner Points we improve the ratio (Δ+1)/2 to 1+ln(Δ−1).
• For Steiner Forest with Minimum Number of Steiner Points we improve the ratio 2(Δ−1) to Δ.
摘要
•We consider connectivity problems on unit-disc graphs in a convex metric space.•Let Δ be the maximum number of independent points in a unit ball.•For Steiner Tree with Minimum Number of Steiner Points we improve the ratio (Δ+1)/2 to 1+ln(Δ−1).•For Steiner Forest with Minimum Number of Steiner Points we improve the ratio 2(Δ−1) to Δ.
论文关键词：Wireless networks,Unit-disc graph,Steiner tree,Steiner forest,2-connectivity,Approximation algorithms
论文评审过程：Received 10 March 2015, Revised 1 August 2018, Accepted 1 August 2018, Available online 6 August 2018, Version of Record 21 September 2018.
论文官网地址：https://doi.org/10.1016/j.jcss.2018.08.001
