Premium
The tree center problems and the relationship with the bottleneck knapsack problems
Author(s) -
Shioura Akiyoshi,
Shigeno Maiko
Publication year - 1997
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/(sici)1097-0037(199703)29:2<107::aid-net4>3.0.co;2-n
Subject(s) - knapsack problem , bottleneck , center (category theory) , tree (set theory) , tree network , vertex (graph theory) , computer science , mathematical optimization , relation (database) , mathematics , combinatorics , time complexity , graph , data mining , chemistry , embedded system , crystallography
The tree center problems are designed to find a subtree minimizing the maximum distance from any vertex. This paper shows that these problems in a tree network are related to the bottleneck knapsack problems and presents linear‐time algorithms for the tree center problems by using the relation. © 1997 John Wiley & Sons, Inc. Networks, 29: 107–110, 1997