On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
From MaRDI portal
Publication:5901067
DOI10.1016/j.dam.2009.01.011zbMath1231.05193MaRDI QIDQ5901067
Marisa Gutierrez, Liliana Alcón, Celina M. Herrera de Figueiredo, Luérbio Faria
Publication date: 13 August 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: http://sedici.unlp.edu.ar/handle/10915/82445
NP-complete; approximation algorithms; clique graphs; clique-Helly graphs; Max SNP-hard; hereditary clique-Helly graphs
05C35: Extremal problems in graph theory
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68W25: Approximation algorithms
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The node-deletion problem for hereditary properties is NP-complete
- Optimization, approximation, and complexity classes
- Some APX-completeness results for cubic graphs
- Clique Graph Recognition Is NP-Complete
- Topics in Intersection Graph Theory
- Graph Classes: A Survey
- The approximation of maximum subgraph problems