On the recognition of neighborhood inclusion posets

Volver a la Vista simple
dc.conicet.fuenteElsevier
dc.conicet.organizacionUniversidad Nacional de La Plata
dc.conicet.organizacionConsejo Nacional de Investigaciones Científicas y Técnicas
dc.conicet.paisOrganizacionArgentina
dc.conicet.paisOrganizacionArgentina
dc.conicet.produccionid6867270
dc.contributor.authorde Caria, Pablo Jesús
dc.date.accessioned2018-06-22T20:43:27Z
dc.date.available2018-06-22T20:43:27Z
dc.date.issued2017-11
dc.date.updated2018-06-22T15:05:02Z
dc.description.abstractLet G be a simple graph. When we order the different closed neighborhoods of G by inclusion, the resulting poset is called the neighborhood inclusion poset. In this paper, we show that the problem of determining whether a poset is a neighborhood inclusion poset is NP-complete. We also apply this result to prove the NP-completeness of another problem about clique trees of chordal graphs and compatible trees of dually chordal graphs.es
dc.description.filFil: de Caria, Pablo Jesús. Universidad Nacional de La Plata; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.formatapplication/pdfes
dc.identifier.citationde Caria, Pablo Jesús; On the recognition of neighborhood inclusion posets; Elsevier Science; Electronic Notes in Discrete Mathematics; 62; 11-2017; 285-290es
dc.identifier.institucionalCONICET
dc.identifier.issn1571-0653es
dc.identifier.repoCONICET Digital
dc.identifier.urihttp://hdl.handle.net/11336/49798
dc.journal.ciudadAmsterdames
dc.journal.pagination285-290es
dc.journal.paisPaíses Bajoses
dc.journal.titleElectronic Notes in Discrete Mathematicses
dc.journal.volume62es
dc.language.isoenges
dc.publisherElsevier Sciencees
dc.relation.alternativeidinfo:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S1571065317302883
dc.relation.alternativeidinfo:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.endm.2017.10.049
dc.relation.alternativeidinfo:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S1571065317302883
dc.rightsinfo:eu-repo/semantics/openAccess*
dc.rights.urihttps://creativecommons.org/licenses/by-nc-nd/2.5/ar/*
dc.subjectChordal Graphes
dc.subjectClique Treees
dc.subjectCompatible Treees
dc.subjectDually Chordal Graphes
dc.subjectNeighborhood Inclusiones
dc.subjectPosetes
dc.subject.classificationMatemática Puraes
dc.subject.classificationMatemáticases
dc.subject.classificationCIENCIAS NATURALES Y EXACTASes
dc.titleOn the recognition of neighborhood inclusion posetses
dc.typeinfo:eu-repo/semantics/article
dc.typeinfo:ar-repo/semantics/artículo
dc.typeinfo:eu-repo/semantics/publishedVersion

Archivos

Bloque original

Miniatura
Nombre:
CONICET_Digital_Nro.0154be73-2249-4e41-9ea9-a266b34f27bb_A.pdf
Tamaño:
185.57 KB
Formato:
Adobe Portable Document Format
Descargar

Colecciones

Articulos(CCT - LA PLATA)
Volver a la Vista simple