The caterpillar-packing polytope
A caterpillar is a connected 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 vertex-disjoint (not necessarily induced) subgraphs of G such that each subgraph is a caterpillar. In this work we consider the set of...
Guardado en:
Autor principal: | |
---|---|
Publicado: |
2017
|
Materias: | |
Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v245_n_p4_Marenco http://hdl.handle.net/20.500.12110/paper_0166218X_v245_n_p4_Marenco |
Aporte de: |
id |
paper:paper_0166218X_v245_n_p4_Marenco |
---|---|
record_format |
dspace |
spelling |
paper:paper_0166218X_v245_n_p4_Marenco2023-06-08T15:15:36Z The caterpillar-packing polytope Marenco, Javier Leonardo Caterpillar-packing Facets Integer programming Connected graph Cutting problems Facets Feasible solution Natural integer Polytopes Subgraphs Vertex disjoint Graph theory A caterpillar is a connected 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 vertex-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. © 2017 Elsevier B.V. Fil:Marenco, J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2017 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v245_n_p4_Marenco http://hdl.handle.net/20.500.12110/paper_0166218X_v245_n_p4_Marenco |
institution |
Universidad de Buenos Aires |
institution_str |
I-28 |
repository_str |
R-134 |
collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
topic |
Caterpillar-packing Facets Integer programming Connected graph Cutting problems Facets Feasible solution Natural integer Polytopes Subgraphs Vertex disjoint Graph theory |
spellingShingle |
Caterpillar-packing Facets Integer programming Connected graph Cutting problems Facets Feasible solution Natural integer Polytopes Subgraphs Vertex disjoint Graph theory Marenco, Javier Leonardo The caterpillar-packing polytope |
topic_facet |
Caterpillar-packing Facets Integer programming Connected graph Cutting problems Facets Feasible solution Natural integer Polytopes Subgraphs Vertex disjoint Graph theory |
description |
A caterpillar is a connected 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 vertex-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. © 2017 Elsevier B.V. |
author |
Marenco, Javier Leonardo |
author_facet |
Marenco, Javier Leonardo |
author_sort |
Marenco, Javier Leonardo |
title |
The caterpillar-packing polytope |
title_short |
The caterpillar-packing polytope |
title_full |
The caterpillar-packing polytope |
title_fullStr |
The caterpillar-packing polytope |
title_full_unstemmed |
The caterpillar-packing polytope |
title_sort |
caterpillar-packing polytope |
publishDate |
2017 |
url |
https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v245_n_p4_Marenco http://hdl.handle.net/20.500.12110/paper_0166218X_v245_n_p4_Marenco |
work_keys_str_mv |
AT marencojavierleonardo thecaterpillarpackingpolytope AT marencojavierleonardo caterpillarpackingpolytope |
_version_ |
1768544773200674816 |