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: | |
---|---|
Formato: | JOUR |
Materias: | |
Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_0166218X_v245_n_p4_Marenco |
Aporte de: |
id |
todo:paper_0166218X_v245_n_p4_Marenco |
---|---|
record_format |
dspace |
spelling |
todo:paper_0166218X_v245_n_p4_Marenco2023-10-03T15:03:46Z The caterpillar-packing polytope Marenco, J. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, J. 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. |
format |
JOUR |
author |
Marenco, J. |
author_facet |
Marenco, J. |
author_sort |
Marenco, J. |
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 |
url |
http://hdl.handle.net/20.500.12110/paper_0166218X_v245_n_p4_Marenco |
work_keys_str_mv |
AT marencoj thecaterpillarpackingpolytope AT marencoj caterpillarpackingpolytope |
_version_ |
1782029889058111488 |