Premium
On a tree‐shaped facility location problem of Minieka
Author(s) -
Rabinovitch Ramon,
Tamir Arie
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.3230220602
Subject(s) - facility location problem , tree (set theory) , node (physics) , computer science , time complexity , mathematical optimization , mathematics , combinatorics , algorithm , physics , quantum mechanics
Minieka and Hakimi et al. considered the problem of locating a tree‐shaped facility of a given length in a tree network, with the objective of maximizing the sum of node distances from this facility. They stated the complexity of the model as an open problem. We prove that it is NP‐complete and provide a pseudopolynomial time algorithm.