Abstract:
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.
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 Department, FCEyN, University of Buenos Aires, Argentina
|
Palabras clave: | Caterpillar-packing; Facets; Integer programming; Connected graph; Cutting problems; Facets; Feasible solution; Natural integer; Polytopes; Subgraphs; Vertex disjoint; Graph theory |
Año: | 2017
|
Volumen: | 245
|
Página de inicio: | 4
|
Página de fin: | 15
|
DOI: |
http://dx.doi.org/10.1016/j.dam.2017.03.018 |
Título revista: | Discrete Applied Mathematics
|
Título revista abreviado: | Discrete Appl Math
|
ISSN: | 0166218X
|
CODEN: | DAMAD
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v245_n_p4_Marenco |
Referencias:
- Baldacci, R., Dell'Amico, M., Salazar González, J., The capacitated m-ring-star problem (2007) Oper. Res., 55 (6), pp. 1147-1162
- Bondy, A., Murty, U., (2008) Graph Theory, Springer-Verlag Graduate Texts in Mathematics, 244
- Calvete, H., Galé, C., Iranzo, J., An efficient evolutionary algorithm for the ring star problem (2013) European J. Oper. Res., 231 (1), pp. 22-33
- Dias, T., de Sousa, G., Macambira, E., Cabral, L., Fampa, M., (2006), An efficient heuristic for the ring star problem, in: Proceedings of the 5th International Workshop on Experimental Algorithms WEA 2006; Dinneen, M., Khosravani, M., A linear time algorithm for the minimum spanning caterpillar problem for bounded treewidth graphs (2010), Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity; Dinneen, M., Khosravani, M., Hardness of approximation and integer programming frameworks for searching for caterpillar trees (2011), pp. 145-150. , Proceedings of the Seventeenth Computing on The Australasian Theory Symposium; Kedad-Sidhoum, S., Nguyen, V., An exact algorithm for solving the ring star problem (2010) Optimization, 59 (1), pp. 125-140
- 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) Optim. Eng., 16 (3), pp. 605-632
- Marenco, J., The caterpillar-packing polytope (2015) Electron. Notes Discrete Math., 50, pp. 47-52
- Naji-Azimi, Z., Salari, M., Toth, P., A heuristic procedure for the capacitated m-ring-star problem (2010) European J. Oper. Res., 207 (3), pp. 1227-1234
- Rinaldi, F., Franz, A., A two-dimensional strip cutting problem with sequencing constraint (2007) European J. Oper. Res., 183, pp. 1371-1384
- Simonetti, L., Frota, Y., de Souza, C.C., (2009), pp. 48-51. , An exact method for the minimum caterpillar spanning problem, in: Proceedings of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization; Simonetti, L., Frota, Y., de Souza, C.C., Upper and lower bounding procedures for the minimum caterpillar spanning problem (2009) Electron. Notes Discrete Math., 35, pp. 83-88
- Sundar, K., Rathinam, S., Multiple depot ring star problem: A polyhedral study and exact algorithm arXiv:1407.5080; Zhang, Z., Qin, H., Lim, A., A memetic algorithm for the capacitated m-ring-star problem (2014) Appl. Intell., 40 (2), pp. 305-321
Citas:
---------- APA ----------
(2017)
. The caterpillar-packing polytope. Discrete Applied Mathematics, 245, 4-15.
http://dx.doi.org/10.1016/j.dam.2017.03.018---------- CHICAGO ----------
Marenco, J.
"The caterpillar-packing polytope"
. Discrete Applied Mathematics 245
(2017) : 4-15.
http://dx.doi.org/10.1016/j.dam.2017.03.018---------- MLA ----------
Marenco, J.
"The caterpillar-packing polytope"
. Discrete Applied Mathematics, vol. 245, 2017, pp. 4-15.
http://dx.doi.org/10.1016/j.dam.2017.03.018---------- VANCOUVER ----------
Marenco, J. The caterpillar-packing polytope. Discrete Appl Math. 2017;245:4-15.
http://dx.doi.org/10.1016/j.dam.2017.03.018