|
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.
Received: 29.12.2006
Citation:
V. V. Lepin, “Algorithms for solution $k$-Star Hub Problem for trees and series-parallel graphs”, Tr. Inst. Mat., 15:2 (2007), 48–57
Linking options:
https://www.mathnet.ru/eng/timb97 https://www.mathnet.ru/eng/timb/v15/i2/p48
|
Statistics & downloads: |
Abstract page: | 209 | Full-text PDF : | 159 | References: | 34 |
|