A polyhedral intersection theorem for capacitated spanning trees

A polyhedral intersection theorem for capacitated spanning trees

0.00 Avg rating0 Votes
Article ID: iaor19921851
Country: United States
Volume: 17
Issue: 2
Start Page Number: 398
End Page Number: 410
Publication Date: May 1992
Journal: Mathematics of Operations Research
Authors: ,
Keywords: networks
Abstract:

In a two-capacitated spanning tree of a complete graph with a distinguished root vertex v, every component of the induced subgraph on Vz.drule;{v} has at most two vertices. The authors give a complete, nonredundant characterization of the polytope defined by teh convex hull of the incidence vectors of two-capacitated spanning trees. This polytope is the intersection of the spanning tree polytope on the given graph and the matching polytope on the subgraph induced by removing the root node and its incident edges. This result is one of very few known cases in which the intersection of two integer polyhedra yields another integer polyhedron. The authors also give a complete polyhedral characterization of a related polytope, the 2-capacitated forest polytope.

Reviews

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