Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By $(d, h)$-tree-decomposition, I mean to divide the vertices $V$ into $k$ trees, such that the height of each tree is $h$, and each non-leaf node has $d$ children. I know it is definitely $\text{NP}$-Hard, since minimum $(1, |V|-1)$-tree-decomposition is the minimum Hamilton path. But are there any good approximation algorithms?
Approximate minimum-weighted tree decomposition on complete graphs
algorithms;complexity theory;graphs;graph theory;approximation