Mostrar el registro sencillo del ítem

dc.contributor.author
Alcón, Liliana Graciela  
dc.contributor.author
Bonomo, Flavia  
dc.contributor.author
Mazzoleni, María Pía  
dc.date.available
2018-08-24T17:08:20Z  
dc.date.issued
2017-07  
dc.identifier.citation
Alcón, Liliana Graciela; Bonomo, Flavia; Mazzoleni, María Pía; Vertex Intersection Graphs of Paths on a Grid: Characterization Within Block Graphs; Springer Tokyo; Graphs And Combinatorics; 33; 4; 7-2017; 653-664  
dc.identifier.issn
0911-0119  
dc.identifier.uri
http://hdl.handle.net/11336/57004  
dc.description.abstract
We investigate graphs that can be represented as vertex intersections of horizontal and vertical paths in a grid, the so called B0-VPG graphs. Recognizing this class is an NP-complete problem. Although, there exists a polynomial time algorithm for recognizing chordal B0-VPG graphs. In this paper, we present a minimal forbidden induced subgraph characterization of B0-VPG graphs restricted to block graphs. As a byproduct, the proof of the main theorem provides an alternative certifying recognition and representation algorithm for B0-VPG graphs in the class of block graphs.  
dc.format
application/pdf  
dc.language.iso
eng  
dc.publisher
Springer Tokyo  
dc.rights
info:eu-repo/semantics/openAccess  
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/  
dc.subject
Block Graphs  
dc.subject
Forbidden Induced Subgraphs  
dc.subject
Paths on A Grid  
dc.subject
Vertex Intersection Graphs  
dc.subject.classification
Matemática Pura  
dc.subject.classification
Matemáticas  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
dc.title
Vertex Intersection Graphs of Paths on a Grid: Characterization Within Block 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
2018-08-23T18:57:25Z  
dc.journal.volume
33  
dc.journal.number
4  
dc.journal.pagination
653-664  
dc.journal.pais
Japón  
dc.journal.ciudad
Tokyo  
dc.description.fil
Fil: Alcón, Liliana Graciela. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de La Plata. Facultad de Ciencias Exactas. Departamento de Matemáticas; Argentina  
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; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina  
dc.description.fil
Fil: Mazzoleni, María Pía. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de La Plata. Facultad de Ciencias Exactas. Departamento de Matemáticas; Argentina  
dc.journal.title
Graphs And Combinatorics  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/https://dx.doi.org/10.1007/s00373-017-1791-6  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://link.springer.com/article/10.1007%2Fs00373-017-1791-6  

Archivos asociados
Thumbnail
 
Tamaño: 775.0Kb
Formato: PDF
.