Navegar

Colección

Datos Estadísticas

Artículo

El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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