Artículo
Abstract:
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.
Registro:
| Documento: | Artículo |
| Título: | The caterpillar-packing polytope |
| Autor: | Marenco, J. |
| Filiación: | Sciences Institute, National University of General Sarmiento, Argentina Computer Science Dept., FCEyN, University of Buenos Aires, Argentina |
| Palabras clave: | Caterpillar-packing; Facets |
| Año: | 2015 |
| Volumen: | 50 |
| Página de inicio: | 47 |
| Página de fin: | 52 |
| DOI: | http://dx.doi.org/10.1016/j.endm.2015.07.009 |
| Título revista: | Electronic Notes in Discrete Mathematics |
| Título revista abreviado: | Electron. Notes Discrete Math. |
| ISSN: | 15710653 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v50_n_p47_Marenco |
Referencias:
- Labbé, M., Laporte, G., Martín, I., González, J., The ring star problem: polyhedral analysis and exact algorithm (2004) Networks, 43, pp. 177-189
- Lekkerkerker, C., Boland, J., Representation of a finite graph by a set of intervals on the real line (1962) Fund. Math., 51, pp. 45-64
- Lucero, S., Marenco, J., Martínez, F., An integer programming approach for the 2-schemes strip cutting problem with a sequencing constraint (2015) Optimization and Engineering, , (in press)
- Rinaldi, F., Franz, A., A two-dimensional strip cutting problem with sequencing constraint (2007) European Journal of Operational Research, 183, pp. 1371-1384
- Simonetti, L., Frota, Y., de Souza, C.C., Upper and lower bounding procedures for the minimum caterpillar spanning problem (2009) Eletronic Notes in Discrete Mathematics, 35, pp. 83-88
Citas:
---------- APA ----------
(2015) . The caterpillar-packing polytope. Electronic Notes in Discrete Mathematics, 50, 47-52.http://dx.doi.org/10.1016/j.endm.2015.07.009
---------- CHICAGO ----------
Marenco, J. "The caterpillar-packing polytope" . Electronic Notes in Discrete Mathematics 50 (2015) : 47-52.http://dx.doi.org/10.1016/j.endm.2015.07.009
---------- MLA ----------
Marenco, J. "The caterpillar-packing polytope" . Electronic Notes in Discrete Mathematics, vol. 50, 2015, pp. 47-52.http://dx.doi.org/10.1016/j.endm.2015.07.009
---------- VANCOUVER ----------
Marenco, J. The caterpillar-packing polytope. Electron. Notes Discrete Math. 2015;50:47-52.http://dx.doi.org/10.1016/j.endm.2015.07.009
