Geodesic
Algorithms for solution $k$-Star Hub Problem for trees and series-parallel graphs
Trudy Instituta matematiki, Tome 15 (2007) no. 2, pp. 48-57 
V. V. Lepin. Algorithms for solution $k$-Star Hub Problem for trees and series-parallel graphs. Trudy Instituta matematiki, Tome 15 (2007) no. 2, pp. 48-57. http://geodesic.mathdoc.fr/item/TIMB_2007_15_2_a5/
@article{TIMB_2007_15_2_a5,
     author = {V. V. Lepin},
     title = {Algorithms for solution $k${-Star} {Hub} {Problem} for trees and series-parallel graphs},
     journal = {Trudy Instituta matematiki},
     pages = {48--57},
     year = {2007},
     volume = {15},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2007_15_2_a5/}
}
TY  - JOUR
AU  - V. V. Lepin
TI  - Algorithms for solution $k$-Star Hub Problem for trees and series-parallel graphs
JO  - Trudy Instituta matematiki
PY  - 2007
SP  - 48
EP  - 57
VL  - 15
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMB_2007_15_2_a5/
LA  - ru
ID  - TIMB_2007_15_2_a5
ER  - 
%0 Journal Article
%A V. V. Lepin
%T Algorithms for solution $k$-Star Hub Problem for trees and series-parallel graphs
%J Trudy Instituta matematiki
%D 2007
%P 48-57
%V 15
%N 2
%U http://geodesic.mathdoc.fr/item/TIMB_2007_15_2_a5/
%G ru
%F TIMB_2007_15_2_a5

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] Blasum U., Hochstattler W., Oertel P., Steiner diagrams and $k$-star hubs, Report No. 00.384, Angewandte mathematik und informatik Universität zu Köln, 1999 | MR

[2] Hochstattler W., Oertel P., The 5-Star-Hub-Problem is NP-complete, Report No. 00.385, Angewandte mathematik und informatik Universität zu Köln, 2000

[3] Bern M.W., Lawler E.L., Wong A.L., “Linear time computation of optimal subgraphs of decomposable graphs”, J. Algorithms, 8 (1987), 216–235 | DOI | MR | Zbl

[4] Borie R.B., Parker R.G., Tovey C.A., “Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families”, Algorithmica, 7 (1992), 555–581 | DOI | MR | Zbl

[5] Kikuno T., Yoshida N., Kakuda Y., “A linear algorithm for the domination number of a series-parallel graph”, Disc. Appl. Math., 5 (1983), 299–311 | DOI | MR | Zbl

[6] Takamizawa K., Nishizeki T., Saito N., “Linear-time computability of combinatorial problems on series-parallel graphs”, J. ACM, 29 (1982), 623–641 | DOI | MR | Zbl

[7] Duffin R.J., “Topology of series-parallel graphs”, J. Math. Anal. Appl., 10 (1965), 303–318 | DOI | MR | Zbl

[8] Valdes J., Tarjan R.E., Lawler E.L., “The recognition of series parallel digraphs”, SIAM J. Comput., 11 (1982), 298–313 | DOI | MR | Zbl