Hardness and methods to solve CLIQUE

DOI10.1007/BF02948987MaRDI QIDQ5959359zbMATH OpenOpenAlexFDO

Authors Daming Zhu, Junfeng Luan, Shaohan Ma

Publication date 17 October 2002

Published in Journal of Computer Science and Technology (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02948987

zbMATH Keywords

CLIQUE

Mathematics Subject Classification ID

Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.) (68N19)

Recommendations

• A branch and bound algorithm for the maximum clique problem
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• A review on algorithms for maximum clique problems
• The maximum clique problem
• A note on the complexity of the maximum edge clique partitioning problem with respect to the clique number

Cites work

• Approximation algorithms for NP-hard problems.
• HEWN: A polynomial algorithm for CLIQUE problem
• scientific article; zbMATH DE number 3489106 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256635 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• On the complexity of approximating the independent set problem
• On the hardness of approximating minimization problems
• Optimization, approximation, and complexity classes
• The complexity of theorem-proving procedures

Cited in

(5)

• Component model for a NP-hard problem
• scientific article; zbMATH DE number 1256714 (Why is no real title available?)
• Clique is hard on average for regular resolution
• scientific article; zbMATH DE number 279581 (Why is no real title available?)
• Hard graphs for the maximum clique problem

Describes a project that uses

Uses Software

• HEWN

This page was built for publication: Hardness and methods to solve CLIQUE

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