Title: Minimum Diameter Vertex-Weighted Steiner Tree
Abstract: Let $$G = (V, E, w, \rho , \mathcal {T})$$ be a weighted connected graph, where V is the vertex set, E is the edge set, $$\mathcal {T} \subseteq V$$ is a terminal subset, $$w: E \rightarrow \mathbb {R}^{+}$$ is an edge-weight function and $$\rho : V \rightarrow \mathbb {R}^{+}$$ is a vertex-weight function. The weighted diameter of a Steiner tree T in G spanning $$\mathcal {T}$$ is referred to as the longest weighted tree distance on T between terminals. The objective of the Minimum Diameter Vertex-Weighted Steiner Tree Problem (MDWSTP) is to construct a Steiner tree in G spanning $$\mathcal {T}$$ to minimize the weighted diameter. In this paper, we study the MDWSTP in two classes of parameterized graphs, $$\langle \mathcal {T}, \mu \rangle $$ -PG and $$( \mathcal {T}, \lambda )$$ -PG, which are introduced from the perspective of the parameterized upper bound on the ratio of two vertex-weights, and a weaker version of the parameterized triangle inequality, respectively, and achieve simple approximation algorithms. For the MDWSTP in edge-weighted $$\langle \mathcal {T}, \mu \rangle $$ -PG, we obtain a $$\frac{\mu + 1}{2}$$ -factor approximation algorithm where $$\frac{\mu + 1}{2}$$ is tight. For the MDWSTP in vertex-weighted $$( \mathcal {T}, \lambda )$$ -PG, we first obtain a $$\lambda $$ -factor approximation algorithm where $$\lambda $$ is tight, and then develop a slightly improved approximation algorithm.
Publication Year: 2020
Publication Date: 2020-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot