Parameterized Approximations for the Minimum Diameter Vertex-Weighted Steiner Tree Problem in Graphs with Parameterized Weights

Let G = (V,E,w,Ï ,X) be a weighted undirected connected graph, where V is the set of vertices, E is the set of edges, X ⊆ V is a subset of terminals, w(e) > 0,∀e ∈ E denotes the weight associated with edge e, and Ï (v) > 0,∀v ∈ V denotes the weight associated with vertex v. Let T be a Steiner tree in G to interconnect all terminals in X. For any two terminals, t′,t″ ∈ X, we consider the weighted tree distance on T from t′ to t″, defined as the weight of t″ times the classic tree distance on T from t′ to t″. The longest weighted tree distance on T between terminals is named the weighted diameter of T. The Minimum Diameter Vertex-Weighted Steiner Tree Problem (MDWSTP) asks for a Steiner tree in G of the minimum weighted diameter to interconnect all terminals in X.In this paper, we introduce two classes of parameterized graphs (PG), 〈X,μ〉-PG and (X,λ)-PG, in terms of the parameterized upper bound on the ratio of two vertex weights, and a weaker version of the parameterized triangle inequality, respectively, and present approximation algorithms of a parameterized factor for the MDWSTP in them. For the MDWSTP in an edge-weighted 〈X,μ〉-PG, we present an approximation algorithm of a parameterized factor μ+1 2. For the MDWSTP in a vertex-weighted (X,λ)-PG, we first present a simple approximation algorithm of a parameterized factor λ, where λ is tight when λ ≥ 2, and further develop another approximation algorithm of a slightly improved factor.