The caterpillar-packing polytope

Mostrar todas las versiones(4)

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-pack...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Marenco, J.
Formato: JOUR
Materias:
Caterpillar-packing
Facets
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_15710653_v50_n_p47_Marenco
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_15710653_v50_n_p47_Marenco
record_format dspace
spelling todo:paper_15710653_v50_n_p47_Marenco2023-10-03T16:27:09Z The caterpillar-packing polytope Marenco, J. Caterpillar-packing Facets 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. © 2015 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_15710653_v50_n_p47_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
spellingShingle Caterpillar-packing
Facets
Marenco, J.
The caterpillar-packing polytope
topic_facet Caterpillar-packing
Facets
description 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. © 2015 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_15710653_v50_n_p47_Marenco
work_keys_str_mv AT marencoj thecaterpillarpackingpolytope
AT marencoj caterpillarpackingpolytope
_version_ 1807320605270212608

Ejemplares similares