A minimum-length covering subtree of a tree

A minimum-length covering subtree of a tree

0.00 Avg rating0 Votes
Article ID: iaor19901076
Country: United States
Volume: 37
Issue: 2
Start Page Number: 309
End Page Number: 326
Publication Date: Apr 1990
Journal: Naval Research Logistics
Authors: , , ,
Abstract:

The authors 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.

Reviews

Required fields are marked *. Your email address will not be published.