A minimum‐length covering subtree of a tree

Tae Ung Kim, Timothy J. Lowe, James E. Ward and Richard L. Francis

Naval Research Logistics (NRL), 1990, vol. 37, issue 2, 309-326

Abstract: 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.

Date: 1990
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199004)37:23.0.CO;2-8

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:37:y:1990:i:2:p:309-326

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().