Premium
The generalized P ‐forest problem on a tree network
Author(s) -
Tamir Arie,
Lowe Timothy J.
Publication year - 1992
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230220302
Subject(s) - tree (set theory) , computer science , mathematics , time complexity , tree network , steiner tree problem , mathematical optimization , polynomial , k ary tree , theoretical computer science , combinatorics , tree structure , binary tree , mathematical analysis
In two recent papers, similar multifacility problems on tree networks were studied where facilities are subtrees of the tree. The complexity of the problems was left as open. In this paper, we formulate a general model that includes the above‐cited problems as special cases and give a polynomial algorithm to solve the general model.