The 1-persistency of the clique relaxation of the stable set polytope: A focus on some forbidden structures | ||
| dc.conicet.organizacion | No especifíca | |
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario | |
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario | |
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario | |
| dc.contributor.author | Delle Donne, D. | |
| dc.contributor.author | Escalante, Mariana Silvina | |
| dc.contributor.author | Fekete, Pablo Gabriel | |
| dc.contributor.author | Moroni, Lucía | |
| dc.date.issued | 2026-02 | |
| dc.description.abstract | A polytope P ⊆ [0,1]n is said to have the persistency property if for every vector c ∈ Rn and every c-optimal point x ∈ P, there exists a c-optimal integer point y ∈ P ∩ {0,1}n such that xi = yi for each i ∈ {1,...,n} with xi ∈ {0,1}. In this paper, we consider a relaxation of the persistency property called 1-persistency. We study the family Q of graphs whose clique relaxation of the stable set polytope has 1-persistency, and we refer to them as Q-persistent graphs. We provide sufficient conditions for a graph to be Q-persistent, and identify several graph classes of this family. Motivated by a necessary condition of this property, we introduce the family of (k,U)-umbrella graphs, and study which of them belong to Q. The property of being Q-persistent is a hereditary property for graphs, and then it becomes relevant to study the minimal forbidden structures for the family Q, i.e., minimally not Q-persistent (mnQ) graphs. In this line, we identify some mnQ (k,U)-umbrella graphs and also other forbidden minimal structures for Q-persistency outside this family (named as whale graphs). | es |
| dc.description.fil | Fil: Delle Donne, D.. No especifíca; | |
| dc.description.fil | Fil: Escalante, Mariana Silvina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina | |
| dc.description.fil | Fil: Fekete, Pablo Gabriel. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina | |
| dc.description.fil | Fil: Moroni, Lucía. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Delle Donne, D.; Escalante, Mariana Silvina; Fekete, Pablo Gabriel; Moroni, Lucía; The 1-persistency of the clique relaxation of the stable set polytope: A focus on some forbidden structures; Elsevier Science; Discrete Applied Mathematics; 387; 2-2026; 37-56 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0166-218X | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/286626 | |
| dc.journal.pagination | 37-56 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Discrete Applied Mathematics | es |
| dc.journal.volume | 387 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier Science | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://linkinghub.elsevier.com/retrieve/pii/S0166218X26001125 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2026.02.033 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by/2.5/ar/ | * |
| dc.subject | STABLE SET POLYTOPE | es |
| dc.subject | PERSISTENCY | es |
| dc.subject | INTEGER PROGRAMMING | es |
| dc.subject.classification | Otras Matemáticas | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | The 1-persistency of the clique relaxation of the stable set polytope: A focus on some forbidden structures | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.f5d3cc3f-58da-4190-81a9-77cf3d282a52_B.pdf
- Tamaño:
- 1,014.52 KB
- Formato:
- Adobe Portable Document Format