On dominating set polyhedra of circular interval graphs | ||
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura | |
| 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 | Escuela Politécnica Nacional | |
| dc.contributor.author | Bianchi, Silvia María | |
| dc.contributor.author | Nasini, Graciela Leonor | |
| dc.contributor.author | Tolomei, Paola Beatriz | |
| dc.contributor.author | Torres, Luis Miguel | |
| dc.date.issued | 2021-04 | |
| dc.description.abstract | Clique-node and closed neighborhood matrices of circular interval graphs are circular matrices. The stable set polytope and the dominating set polytope on these graphs are therefore closely related to the set packing polytope and the set covering polyhedron on circular matrices. Eisenbrand et al. [18] take advantage of this relationship to propose a complete linear description of the stable set polytope on circular interval graphs. In this paper we follow similar ideas to obtain a complete description of the dominating set polytope on the same class of graphs. As in the packing case, our results are established for a larger class of covering polyhedra of the form Q ∗ (A, b) := conv {x ∈ Z n + : Ax ≥ b}, with A a circular matrix and b an integer vector. These results also provide linear descriptions of polyhedra associated with several variants of the dominating set problem on circular interval graphs. | es |
| dc.description.fil | Fil: Bianchi, Silvia María. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina | |
| dc.description.fil | Fil: Nasini, Graciela Leonor. 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: Tolomei, Paola Beatriz. 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: Torres, Luis Miguel. Escuela Politécnica Nacional; Ecuador | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Bianchi, Silvia María; Nasini, Graciela Leonor; Tolomei, Paola Beatriz; Torres, Luis Miguel; On dominating set polyhedra of circular interval graphs; Elsevier Science; Discrete Mathematics; 344; 4; 4-2021; 1-25 | es |
| dc.identifier.eissn | 1872-681X | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0012-365X | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/153322 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.number | 4 | es |
| dc.journal.pagination | 1-25 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Discrete Mathematics | es |
| dc.journal.volume | 344 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier Science | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0012365X20304696 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.disc.2020.112283 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://arxiv.org/abs/1712.07057 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/2.5/ar/ | * |
| dc.subject | CIRCULANT MINOR | es |
| dc.subject | CIRCULAR MATRIX | es |
| dc.subject | COVERING POLYHEDRA | es |
| dc.subject | DOMINATING SETS | es |
| dc.subject.classification | Otras Matemáticas | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | On dominating set polyhedra of circular interval graphs | 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.fdc05020-6ba8-4f89-a99e-ef479ff3eff7_V.pdf
- Tamaño:
- 360.03 KB
- Formato:
- Adobe Portable Document Format
- Descripción: