Forest covers and a polyhedral intersection theorem

Forest covers and a polyhedral intersection theorem

0.00 Avg rating0 Votes
Article ID: iaor19891036
Country: Netherlands
Volume: 45
Issue: 1
Start Page Number: 49
End Page Number: 58
Publication Date: Aug 1989
Journal: Mathematical Programming
Authors: ,
Abstract:

A forest cover of a graph is a spanning forest for which each component has at least two nodes. The authors consider the convex hull of incidence vectors of forest covers in a graph and show that this polyhedron is the intersection of the forest polytope and the cover polytope. This polytope has both the spanning tree and perfect matching polytopes as faces. Further, the forest cover polytope remains integral with the addition of the constraint requiring that, for some integer k, exactly k edges be used in the solution.

Reviews

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