Journal article
A minimum-length covering subtree of a tree
Naval research logistics, Vol.37(2), pp.309-326
04/1990
DOI: 10.1002/1520-6750(199004)37:2<309::AID-NAV3220370209>3.0.CO;2-8
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.
Details
- Title: Subtitle
- A minimum-length covering subtree of a tree
- Creators
- Tae Ung Kim - Sungkyunkwan UniversityTimothy J. Lowe - University of IowaJames E. Ward - Purdue University West LafayetteRichard L. Francis - University of Florida
- Resource Type
- Journal article
- Publication Details
- Naval research logistics, Vol.37(2), pp.309-326
- DOI
- 10.1002/1520-6750(199004)37:2<309::AID-NAV3220370209>3.0.CO;2-8
- ISSN
- 0894-069X
- eISSN
- 1520-6750
- Publisher
- Wiley Subscription Services, Inc., A Wiley Company
- Number of pages
- 18
- Language
- English
- Date published
- 04/1990
- Academic Unit
- Business Analytics
- Record Identifier
- 9984963096702771
Metrics
1 Record Views