Artículo
On the recognition of neighborhood inclusion posets
Fecha de publicación:
11/2017
Editorial:
Elsevier Science
Revista:
Electronic Notes in Discrete Mathematics
ISSN:
1571-0653
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
Let 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.
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(CCT - LA PLATA)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Citación
de Caria, Pablo Jesús; On the recognition of neighborhood inclusion posets; Elsevier Science; Electronic Notes in Discrete Mathematics; 62; 11-2017; 285-290
Compartir
Altmétricas