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

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)20-36
Number of pages17
JournalJournal of Computer and System Sciences
Volume123
DOIs
Publication statusPublished - 2022 Feb

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'An improved algorithm for the Steiner tree problem with bounded edge-length'. Together they form a unique fingerprint.

Cite this