On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs

DOI10.1016/J.DAM.2009.01.011MaRDI QIDQ5901067zbMATH OpenOpenAlexFDO

Authors L. Alcón, Luerbio Faria, Celina M. H. de Figueiredo, M. Gutierrez

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

zbMATH Keywords

approximation algorithmsclique graphsNP-completeclique-Helly graphsMax SNP-hardhereditary clique-Helly graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
• Faster recognition of clique-Helly and hereditary clique-Helly graphs
• scientific article; zbMATH DE number 1409177
• On the hereditary (p,q)-Helly property of hypergraphs, cliques, and bicliques
• scientific article; zbMATH DE number 553916

Cites work

• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• scientific article; zbMATH DE number 553916 (Why is no real title available?)
• scientific article; zbMATH DE number 1944140 (Why is no real title available?)
• scientific article; zbMATH DE number 851097 (Why is no real title available?)
• scientific article; zbMATH DE number 1409177 (Why is no real title available?)
• Clique Graph Recognition Is NP-Complete
• Graph Classes: A Survey
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• The approximation of maximum subgraph problems
• The node-deletion problem for hereditary properties is NP-complete
• Topics in Intersection Graph Theory

Cited in

(3)

• On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
• Edge contraction and edge removal on iterated clique graphs
• Reoptimization of maximum weight induced hereditary subgraph problems

This page was built for publication: On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5901067)