On the proper interval completion problem within some chordal subclasses | ||
| dc.conicet.organizacion | Université de Bordeaux | |
| dc.conicet.organizacion | University of Primorska | |
| dc.conicet.organizacion | Universidad Nacional de General Sarmiento | |
| dc.conicet.organizacion | Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura. Escuela de Ciencias Básicas | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación | |
| dc.conicet.organizacion | Universidad Nacional de Rosario | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario | |
| dc.conicet.organizacion | Universidade Federal de Minas Gerais | |
| dc.contributor.author | Dross, François | |
| dc.contributor.author | Hilaire, Claire | |
| dc.contributor.author | Koch, Ivo | |
| dc.contributor.author | Leoni, Valeria Alejandra | |
| dc.contributor.author | Pardal, Nina | |
| dc.contributor.author | Lopez Pujato, María Inés | |
| dc.contributor.author | Fernandes Dos Santos, Vinicius | |
| dc.date.issued | 2025-01 | |
| dc.description.abstract | Given a property (graph class) , a graph G, and an integer k, the -completion problem consists of deciding whether we can turn G into a graph with the property by adding at most k edges to G. The -completion problem is known to be NP-hard for general graphs when is the property of being a proper interval graph (PIG). In this work, we study the PIG-completion problem within different subclasses of chordal graphs. We show that the problem remains NP-complete even when restricted to split graphs. We then turn our attention to positive results and present polynomial time algorithms to solve the PIGcompletion problem when the input is restricted to caterpillar and threshold graphs. We also present an efficient algorithm for the minimum co-bipartite-completion for quasithreshold graphs, which provides a lower bound for the PIG-completion problem within this graph class. | es |
| dc.description.fil | Fil: Dross, François. Université de Bordeaux; Francia | |
| dc.description.fil | Fil: Hilaire, Claire. University of Primorska; Eslovenia | |
| dc.description.fil | Fil: Koch, Ivo. Universidad Nacional de General Sarmiento; Argentina | |
| dc.description.fil | Fil: Leoni, Valeria Alejandra. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura. Escuela de Ciencias Básicas; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina | |
| dc.description.fil | Fil: Pardal, Nina. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación; Argentina | |
| dc.description.fil | Fil: Lopez Pujato, María Inés. Universidad Nacional de Rosario; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina | |
| dc.description.fil | Fil: Fernandes Dos Santos, Vinicius. Universidade Federal de Minas Gerais; Brasil | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Dross, François; Hilaire, Claire; Koch, Ivo; Leoni, Valeria Alejandra; Pardal, Nina; et al.; On the proper interval completion problem within some chordal subclasses; Elsevier Science; Discrete Mathematics; 348; 1; 1-2025; 1-15 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0012-365X | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/266756 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.number | 1 | es |
| dc.journal.pagination | 1-15 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Discrete Mathematics | es |
| dc.journal.volume | 348 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier Science | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/https://doi.org/10.1016/j.disc.2024.114274 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0012365X24004059 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by/2.5/ar/ | * |
| dc.subject | bbb | es |
| dc.subject | bb | 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 the proper interval completion problem within some chordal subclasses | 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.c9975d0b-2ad2-4d7b-9ef0-3db08aa32899_B.pdf
- Tamaño:
- 824.59 KB
- Formato:
- Adobe Portable Document Format