Algorithms for solution $k$-Star Hub Problem for trees and series-parallel graphs

V. V. Lepin

Trudy Instituta matematiki, Tome 15 (2007) no. 2, pp. 48-57

Résumé

The following problem is considered. The $k$-Star Hub Problem. Input: Given a graph $G=(V,E)$, a nonnegative integer weight function $w_0\colon E\to\mathbb{Z}^+$ on the edges and $k$ nonnegative integer weight functions on the vertices $w_1,\ldots,w_k\colon V\to\mathbb{Z}^+$. Objective: Find a set of edges $F\subseteq E$ and $k$ subsets of the vertices $V_1,\ldots,V_k\subseteq V$ such that for all $e=(u,v)\in E$ either $e\in F$ or for some $i\in\{1,\ldots,k\}$ $\{u,v\}\in V_i$, and $$ \sum_{e\in F}w_0(e)+\sum_{i=1}^k\,\sum_{v\in V_i}w_i(v) $$ is minimal. Linear-time algorithms for this problem when $k$ is fixed and $G$ is a tree or a series-parallel graph are given.