The caterpillar-packing polytope

详细信息    查看全文

• 作者：Javier Marenco ^{jmarenco@ungs.edu.ar" class="auth_mail" title="E-mail the corresponding author}
• 关键词：caterpillar-packing ; facets
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：50
• 期：Complete
• 页码：47-52
• 全文大小：192 K

文摘

A caterpillar is a graph such that the removal of all its vertices with degree 1 results in a path. Given a graph G, a caterpillar-packing of G is a set of disjoint (not necessarily induced) subgraphs of G such that each subgraph is a caterpillar. In this work we consider the set of caterpillar-packings of a graph, which corresponds to feasible solutions of the 2-schemes strip cutting problem with a sequencing constraint (2-SSCPsc) presented by F. Rinaldi and A. Franz in 2007. We study the polytope associated with a natural integer programming formulation of this problem. We explore basic properties of this polytope, including a lifting lemma and several facet-preserving operations on the graph. These results allow us to introduce several families of facet-inducing inequalities.