Mostrar el registro sencillo del ítem

dc.contributor.author
Bonomo, Flavia  
dc.contributor.author
Galby, Esther  
dc.contributor.author
González, Carolina Lucía  
dc.date.available
2021-10-15T17:37:04Z  
dc.date.issued
2020-09  
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  
dc.identifier.issn
0166-218X  
dc.identifier.uri
http://hdl.handle.net/11336/143879  
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.  
dc.format
application/pdf  
dc.language.iso
eng  
dc.publisher
Elsevier Science  
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  
dc.subject
CONTACT B0-VPG  
dc.subject
CONTACT GRAPHS OF PATHS ON A GRID  
dc.subject.classification
Ciencias de la Computación  
dc.subject.classification
Ciencias de la Computación e Información  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
dc.subject.classification
Matemática Aplicada  
dc.subject.classification
Matemáticas  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
dc.title
Characterising circular-arc contact B0–VPG graphs  
dc.type
info:eu-repo/semantics/article  
dc.type
info:ar-repo/semantics/artículo  
dc.type
info:eu-repo/semantics/publishedVersion  
dc.date.updated
2021-09-07T18:28:37Z  
dc.journal.volume
283  
dc.journal.pagination
435-443  
dc.journal.pais
Países Bajos  
dc.journal.ciudad
Amsterdam  
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.journal.title
Discrete Applied Mathematics  
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  

Archivos asociados
Tamaño: 385.9Kb
Formato: PDF
.