An improved algorithm for the Steiner tree problem with bounded edge-length

研究成果: Article同行評審

1 引文 斯高帕斯(Scopus)

摘要

This work firstly studies the Steiner tree problem with bounded edge-length d in which d is the ratio of the maximum edge cost to the minimum edge cost. This work analyzes the algorithm of Byrka et al. [19] and shows that the approximation ratio of [Formula presented] for general graphs and approximation ratio of [Formula presented] for quasi-bipartite graphs. The algorithm implies approximation ratio of 1.162+ϵ for the problem on complete graphs with edge distances 1 and 2. This finding represents an improvement upon the previous best approximation ratio of 1.25. This work then presents a combinatorial two-phase heuristic for the general Steiner tree in greedy strategy that achieves an approximation ratio of 1.4295.

原文English
頁(從 - 到)20-36
頁數17
期刊Journal of Computer and System Sciences
123
DOIs
出版狀態Published - 2022 2月

All Science Journal Classification (ASJC) codes

  • 理論電腦科學
  • 電腦網路與通信
  • 計算機理論與數學
  • 應用數學

指紋

深入研究「An improved algorithm for the Steiner tree problem with bounded edge-length」主題。共同形成了獨特的指紋。

引用此