Forest covers and a polyhedral intersection theorem |
| |
Authors: | A B Gamble W R Pulleyblank |
| |
Institution: | (1) Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada |
| |
Abstract: | Aforest cover of a graph is a spanning forest for which each component has at least two nodes. We 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 integerk, exactlyk edges be used in the solution.Research done while thae authors were visiting the Institut für Ökonometrie und Operations Research, Universität Bonn, West Germany.Financial support provided by the Natural Sciences and Engineering Research Council, Canada and the German Research Association (Deutsche Forschungsgemeneinschaft, SFB 303). |
| |
Keywords: | forest edge covers forest polytope cover polytope |
本文献已被 SpringerLink 等数据库收录! |
|