Approximation algorithms for solving the heterogeneous rooted tree/path cover problems

Pengxiang Pan (), Junran Lichen (), Ping Yang () and Jianping Li ()
Additional contact information
Pengxiang Pan: Yunnan University
Junran Lichen: Beijing University of Chemical Technology
Ping Yang: Yunnan University
Jianping Li: Yunnan University

Journal of Combinatorial Optimization, 2025, vol. 49, issue 3, No 12, 19 pages

Abstract: Abstract In this paper, we consider the heterogeneous rooted tree cover (HRTC) problem, which further generalizes the rooted tree cover problem. Specifically, given a complete graph $$G=(V,E; w,f; r)$$ G = ( V , E ; w , f ; r ) and k construction teams, having nonuniform construction speeds $$\lambda _{1}$$ λ 1 , $$\lambda _{2}$$ λ 2 , $$\ldots $$ … , $$\lambda _{k}$$ λ k , where $$r\in V$$ r ∈ V is a fixed common root, $$w:E\rightarrow {\mathbb {R}}^{+}$$ w : E → R + is an edge-weight function, satisfying the triangle inequality, and $$f:V\rightarrow {\mathbb {R}}^{+}_{0}$$ f : V → R 0 + (i.e., $${\mathbb {R}}^{+}\cup \{0\})$$ R + ∪ { 0 } ) is a vertex-weight function with $$f(r)=0$$ f ( r ) = 0 , we are asked to find k trees for these k construction teams, each tree having the same root r, and collectively covering all vertices in V, the objective is to minimize the maximum completion time of k construction teams, where the completion time of each team is the total construction weight of its related tree divided by its construction speed. In addition, substituting k paths for k trees in the HRTC problem, we also consider the heterogeneous rooted path cover (HRPC) problem. Our main contributions are as follows. (1) Given any small constant $$\delta >0$$ δ > 0 , we first design a $$58.3286(1+\delta )$$ 58.3286 ( 1 + δ ) -approximation algorithm to solve the HRTC problem, and this algorithm runs in time $$O(n^{2}(n+\frac{\log n}{\delta })+\log (w(E)+f(V)))$$ O ( n 2 ( n + log n δ ) + log ( w ( E ) + f ( V ) ) ) . Meanwhile, we present a simple $$116.6572(1+\delta )$$ 116.6572 ( 1 + δ ) -approximation algorithm to solve the HRPC problem, whose time complexity is the same as the preceding algorithm. (2) We provide a $$\max \{2\rho , 2+\rho -\frac{2}{k}\}$$ max { 2 ρ , 2 + ρ - 2 k } -approximation algorithm to resolve the HRTC problem, and that algorithm runs in time $$O(n^{2})$$ O ( n 2 ) , where $$\rho $$ ρ is the ratio of the largest team speed to the smallest one. At the same time, we can prove that the preceding $$\max \{2\rho , 2+\rho -\frac{2}{k}\}$$ max { 2 ρ , 2 + ρ - 2 k } -approximation algorithm also resolves the HRPC problem.

Keywords: Rooted tree/path cover; Nonuniform speeds; Approximation algorithms; Complexity of algorithms (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01278-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:49:y:2025:i:3:d:10.1007_s10878-025-01278-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01278-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().