Vertex Intersection Graphs of Paths on a Grid: Characterization Within Block Graphs

dc.creatorAlcón, Liliana Graciela
dc.creatorBonomo, Flavia
dc.creatorMazzoleni, María Pía
dc.date.accessioned2018-08-24T17:08:20Z
dc.date.available2018-08-24T17:08:20Z
dc.date.created2018-08-24T17:08:20Z
dc.date.issued2017-07
dc.identifierAlcó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.identifier0911-0119
dc.identifierhttp://hdl.handle.net/11336/57004
dc.identifierCONICET Digital
dc.identifierCONICET
dc.description.abstractWe 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.languageeng
dc.publisherSpringer Tokyo
dc.relationinfo:eu-repo/semantics/altIdentifier/doi/https://dx.doi.org/10.1007/s00373-017-1791-6
dc.relationinfo:eu-repo/semantics/altIdentifier/url/https://link.springer.com/article/10.1007%2Fs00373-017-1791-6
dc.rightshttps://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.rightsinfo:eu-repo/semantics/restrictedAccess
dc.subjectBlock Graphs
dc.subjectForbidden Induced Subgraphs
dc.subjectPaths on A Grid
dc.subjectVertex Intersection Graphs
dc.titleVertex Intersection Graphs of Paths on a Grid: Characterization Within Block Graphs
dc.typeinfo:eu-repo/semantics/article
dc.typeinfo:ar-repo/semantics/artículo
dc.typeinfo:eu-repo/semantics/publishedVersion


Este ítem pertenece a la siguiente institución