| Journal: | Pesquisa operacional |
| Database: | PERIÓDICA |
| System number: | 000313086 |
| ISSN: | 0101-7438 |
| Authors: | Bonomo, Flavia1 Duran, Guillermo2 |
| Institutions: | 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 |
| Year: | 2004 |
| Season: | Sep-Dic |
| Volumen: | 24 |
| Number: | 3 |
| Pages: | 413-434 |
| Country: | Brasil |
| Language: | Inglés |
| Document type: | Artículo |
| Approach: | Experimental |
| English abstract | 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 |
| Keyword: | 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 |
| Full text: | Texto completo (Ver HTML) |
