The caterpillar-packing polytope

Mostrar todas las versiones(4)

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

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Marenco, J.
Formato: JOUR
Materias:
Caterpillar-packing
Facets
Integer programming
Connected graph
Cutting problems
Feasible solution
Natural integer
Polytopes
Subgraphs
Vertex disjoint
Graph theory
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_0166218X_v245_n_p4_Marenco
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
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_ 1807323115387092992

Ejemplares similares