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

Wei Ding, Guangting Chen (), Ke Qiu () and Yu Zhou ()
Additional contact information
Wei Ding: Nanxun Innovation Institute, and School of Computer Science and Technology, Zhejiang University of Water Resources and Electric Power, Hangzhou 310018, P. R. China
Guangting Chen: Zhejiang University of Water Resources and Electric Power, Hangzhou 310018, P. R. China
Ke Qiu: Department of Computer Science, Brock University, St. Catharines, Canada
Yu Zhou: College of Data Science, Taiyuan University of Technology, Shanxi Province 030024, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2025, vol. 42, issue 04, 1-19

Abstract: 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.

Keywords: Steiner tree; diameter; vertex-weighted; parameterized (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595924500258
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:42:y:2025:i:04:n:s0217595924500258

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595924500258

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().