The caterpillar-packing polytope
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...
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
Elsevier B.V.
2017
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 05659caa a22006017a 4500 | ||
|---|---|---|---|
| 001 | PAPER-13074 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518204320.0 | ||
| 008 | 190410s2017 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-85018741819 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 030 | |a DAMAD | ||
| 100 | 1 | |a Marenco, J. | |
| 245 | 1 | 4 | |a The caterpillar-packing polytope |
| 260 | |b Elsevier B.V. |c 2017 | ||
| 270 | 1 | 0 | |m Marenco, J.; Computer Science Department, FCEyN, University of Buenos AiresArgentina; email: jmarenco@ungs.edu.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Baldacci, R., Dell'Amico, M., Salazar González, J., The capacitated m-ring-star problem (2007) Oper. Res., 55 (6), pp. 1147-1162 | ||
| 504 | |a Bondy, A., Murty, U., (2008) Graph Theory, Springer-Verlag Graduate Texts in Mathematics, 244 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Marenco, J., The caterpillar-packing polytope (2015) Electron. Notes Discrete Math., 50, pp. 47-52 | ||
| 504 | |a 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 | ||
| 504 | |a Rinaldi, F., Franz, A., A two-dimensional strip cutting problem with sequencing constraint (2007) European J. Oper. Res., 183, pp. 1371-1384 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 520 | 3 | |a 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. |l eng | |
| 593 | |a Sciences Institute, National University of General Sarmiento, Argentina | ||
| 593 | |a Computer Science Department, FCEyN, University of Buenos Aires, Argentina | ||
| 690 | 1 | 0 | |a CATERPILLAR-PACKING |
| 690 | 1 | 0 | |a FACETS |
| 690 | 1 | 0 | |a INTEGER PROGRAMMING |
| 690 | 1 | 0 | |a CONNECTED GRAPH |
| 690 | 1 | 0 | |a CUTTING PROBLEMS |
| 690 | 1 | 0 | |a FACETS |
| 690 | 1 | 0 | |a FEASIBLE SOLUTION |
| 690 | 1 | 0 | |a NATURAL INTEGER |
| 690 | 1 | 0 | |a POLYTOPES |
| 690 | 1 | 0 | |a SUBGRAPHS |
| 690 | 1 | 0 | |a VERTEX DISJOINT |
| 690 | 1 | 0 | |a GRAPH THEORY |
| 773 | 0 | |d Elsevier B.V., 2017 |g v. 245 |h pp. 4-15 |p Discrete Appl Math |x 0166218X |w (AR-BaUEN)CENRE-310 |t Discrete Applied Mathematics | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-85018741819&doi=10.1016%2fj.dam.2017.03.018&partnerID=40&md5=4706d66c221dd156cca1311b3978bcb1 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1016/j.dam.2017.03.018 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_0166218X_v245_n_p4_Marenco |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v245_n_p4_Marenco |y Registro en la Biblioteca Digital |
| 961 | |a paper_0166218X_v245_n_p4_Marenco |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 963 | |a VARI | ||
| 999 | |c 74027 | ||