Characterising circular-arc contact B0–VPG graphs | ||
| 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 | Université de Fribourg | |
| 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.contributor.author | Bonomo, Flavia | |
| dc.contributor.author | Galby, Esther | |
| dc.contributor.author | González, Carolina Lucía | |
| dc.date.issued | 2020-09 | |
| dc.description.abstract | A contact B0–VPG graph is a graph for which there exists a collection of nontrivial pairwise interiorly disjoint horizontal and vertical segments in one-to-one correspondence with its vertex set such that two vertices are adjacent if and only if the corresponding segments touch. It was shown in Deniz et al. (2018) that RECOGNITION is NP-complete for contact B0–VPG graphs. In this paper we present a minimal forbidden induced subgraph characterisation of contact B0–VPG graphs within the class of circular-arc graphs and provide a polynomial-time algorithm for recognising these graphs. | es |
| dc.description.fil | Fil: Bonomo, Flavia. 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: Galby, Esther. Université de Fribourg; Suiza | |
| dc.description.fil | Fil: González, Carolina Lucía. 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.format | application/pdf | es |
| dc.identifier.citation | Bonomo, Flavia; Galby, Esther; González, Carolina Lucía; Characterising circular-arc contact B0–VPG graphs; Elsevier Science; Discrete Applied Mathematics; 283; 9-2020; 435-443 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0166-218X | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/143879 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.pagination | 435-443 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Discrete Applied Mathematics | es |
| dc.journal.volume | 283 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier Science | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2020.01.027 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/abs/pii/S0166218X20300445 | |
| dc.rights | info:eu-repo/semantics/restrictedAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | * |
| dc.subject | CIRCULAR-ARC GRAPHS | es |
| dc.subject | CONTACT B0-VPG | es |
| dc.subject | CONTACT GRAPHS OF PATHS ON A GRID | es |
| dc.subject.classification | Ciencias de la Computación | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.subject.classification | Matemática Aplicada | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | Characterising circular-arc contact B0–VPG 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.8065e0bb-3167-4b98-985f-3045559304b1_A.pdf
- Tamaño:
- 385.95 KB
- Formato:
- Adobe Portable Document Format