The research activities on locating facilities in trees are intense. One of the most important properties of trees, which is useful in designing efficient algorithms, is the existence of a 1-separator between any two disjoint subtrees. This property gives a very nice way to decompose a tree network, i.e., a centroid decomposition spine tree decomposition.
Partial k-trees are a more general class of networks for which similar property is available. Such property is represented by a tree decomposition with treewidth k. Given a tree decomposition of a partial k-tree, there is a k-separator between any two subnetworks represented by two disjoint subtrees of the tree decomposition. The class of partial k-trees includes trees (k=1), series-parallel graphs (k=2), Halin graphs (k=3), and k-terminal graphs. This tree decomposition provides a way to decompose a partial k-tree network. However, not much work has been done to extend the techniques that are used to efficiently solve facility location problems on tree networks, to partial k-trees (except dynamic programming).
We have achieved significant results for location problems in trees. Some of the important results are listed below:
We have developed a two-level tree decomposition data structure over a partial k-tree (k fixed), which can be efficintly built and answer the service cost of a given facility set in a sublinear time. we have also built a subquadratic representation of the inter-vertex distance matrix of a partial k-tree (k fixed).