| Revista: | Pesquisa operacional |
| Base de datos: | PERIÓDICA |
| Número de sistema: | 000313086 |
| ISSN: | 0101-7438 |
| Autors: | Bonomo, Flavia1 Duran, Guillermo2 |
| Institucions: | 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 |
| Any: | 2004 |
| Període: | Sep-Dic |
| Volum: | 24 |
| Número: | 3 |
| Paginació: | 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 |
| Disciplines | Matemáticas, Ciencias de la computación |
| Paraules clau: | 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 |
| Text complet: | Texto completo (Ver HTML) |
