Revista: | Pesquisa operacional |
Base de datos: | PERIÓDICA |
Número de sistema: | 000313086 |
ISSN: | 0101-7438 |
Autores: | Bonomo, Flavia1 Duran, Guillermo2 |
Instituciones: | 1Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales, Buenos Aires. Argentina 2Universidad de Chile, Facultad de Ciencias Físicas y Matemáticas, Santiago de Chile. Chile |
Año: | 2004 |
Periodo: | Sep-Dic |
Volumen: | 24 |
Número: | 3 |
Paginación: | 413-434 |
País: | Brasil |
Idioma: | Inglés |
Tipo de documento: | Artículo |
Enfoque: | Experimental |
Resumen en inglés | A graph is clique-Helly when its cliques satisfy the Helly property. A graph is hereditary clique-Helly when every induced subgraph of it is clique-Helly. The decision problems associated to the stability, chromatic, clique and clique-covering numbers are NP-complete for clique-Helly graphs. In this note, we analyze the complexity of these problems for hereditary clique-Helly graphs. Some of them can be deduced easily by known results. We prove that the clique-covering problem remains NP-complete for hereditary clique-Helly graphs. Furthermore, the decision problems associated to the clique-transversal and the clique-independence numbers are analyzed too. We prove that they remain NP-complete for a smaller class: hereditary clique-Helly split graphs |
Disciplinas: | Matemáticas, Ciencias de la computación |
Palabras clave: | Matemáticas aplicadas, Complejidad computacional, Gráficas Clique-Helly, Teoría de gráficas |
Keyword: | Mathematics, Computer science, Applied mathematics, Computational complexity, Clique-Helly graphs, Graph theory |
Texto completo: | Texto completo (Ver HTML) |