On two restricted ancestors tree problems
We consider rooted minimum spanning tree problems subject to allowed ancestor relations which follow from network security constraints. In one problem nodes are associated with security labels that impose father-child relations. We prove that the feasible solutions define a matroid. In the other problem, there are permission constraints which impose descendant-ancestor relations. We show that even simple special cases of this problem are not approximable within a sub-logarithmic factor, and describe a square root approximation when the edge weights satisfy the triangle inequality. (C) 2010 Elsevier B.V. All rights reserved.
matroid directed minimum spanning tree approximation algorithms