Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
New Advances in Reoptimizing the Minimum Steiner Tree Problem
verfasst von : Davide Bilò, Anna Zych
Erschienen in: Mathematical Foundations of Computer Science 2012
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper we improve the results in the literature concerning the problem of computing the minimum Steiner tree given the minimum Steiner tree for a similar problem instance. Using a
σ
-approximation algorithm computing the minimum Steiner tree from scratch, we provide a
$\left(\frac{3 \sigma-1}{2 \sigma-1}+\epsilon\right)$
and a
$\left(\frac{2 \sigma-1}{\sigma}+\epsilon\right)$
-approximation algorithm for altering the instance by removing a vertex from the terminal set and by increasing the cost of an edge, respectively. If we use the best up to date
σ
= ln 4 +
ε
, our ratios equal 1.218 and 1.279 respectively.