Artículo
Precedence thinness in graphs
Fecha de publicación:
12/2022
Editorial:
Elsevier Science
Revista:
Discrete Applied Mathematics
ISSN:
0166-218X
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
Interval and proper interval graphs are very well-known graph classes, for which there is a wide literature. As a consequence, some generalizations of interval graphs have been proposed, in which graphs in general are expressed in terms of k interval graphs, by splitting the graph in some special way. As a recent example of such an approach, the classes of k-thin and proper k-thin graphs have been introduced generalizing interval and proper interval graphs, respectively. The complexity of the recognition of each of these classes is still open, even for fixed k≥2. In this work, we introduce a subclass of k-thin graphs (resp. proper k-thin graphs), called precedence k-thin graphs (resp. precedence proper k-thin graphs). Concerning partitioned precedence k-thin graphs, we present a polynomial time recognition algorithm based on PQ trees. With respect to partitioned precedence proper k-thin graphs, we prove that the related recognition problem is NP-complete for an arbitrary k and polynomial-time solvable when k is fixed. Moreover, we present a characterization for these classes based on threshold graphs.
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(ICC)
Articulos de INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Articulos de INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Citación
Bonomo, Flavia; de Souza Oliveira, Fabiano; Sampaio Jr., Moysés S.; Szwarcfiter, Jayme L.; Precedence thinness in graphs; Elsevier Science; Discrete Applied Mathematics; 323; 12-2022; 76-95
Compartir
Altmétricas