Premium
A minimum‐length covering subtree of a tree
Author(s) -
Kim Tae Ung,
Lowe Timothy J.,
Ward James E.,
Francis Richard L.
Publication year - 1990
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199004)37:2<309::aid-nav3220370209>3.0.co;2-8
Subject(s) - cardinality (data modeling) , duality (order theory) , cover (algebra) , mathematics , tree (set theory) , point (geometry) , combinatorics , discrete mathematics , mathematical optimization , computer science , geometry , mechanical engineering , engineering , data mining
We show that the problem of finding a minimum‐length covering subtree of a tree can be solved by appropriately modifying a known algorithm for finding a minimum cardinality point cover. Optimality of the unique covering subtree is established by the use of duality theory: a weak duality theorem and a strong duality theorem. The solution provided by the algorithm is shown to solve certain other optimization problems as well.