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

V. V. Lepin

Institute of Mathematics of the National Academy of Sciences of Belarus

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

UDC: 519.1

Received: 29.12.2006