ON TWO APPROXIMATION ALGORITHMS FOR THE CLIQUE PROBLEM

DOI10.1142/S0129054193000080MaRDI QIDQ4286115zbMATH OpenFDO

Authors Iain Stewart

Publication date 27 March 1994

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054193000080

zbMATH Keywords

\(\mathbb{P}\)-completeapproximation algorithmscomplexitygreedy algorithmsoptimization problem MAX-CLIQUE

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A note on the approximation of the MAX CLIQUE problem
• On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• On the approximability of clique and related maximization problems
• Interactive proofs and the hardness of approximating cliques

Cited in

(12)

• Clique is hard to approximate within \(n^{1-\epsilon}\)
• A clique search problem and its application to machine scheduling
• Worst-case analysis of clique MIPs
• A 2-approximation algorithm for the graph 2-clustering problem
• Approximating 2-cliques in unit disk graphs
• A note on improved results for one round distributed clique listing
• scientific article; zbMATH DE number 1332665 (Why is no real title available?)
• Approximating Maximum Clique by Removing Subgraphs
• Approximation Algorithms for the k-Clique Covering Problem
• On approximating the number of k-cliques in sublinear time
• scientific article; zbMATH DE number 956847 (Why is no real title available?)
• Efficient algorithms for clique problems

This page was built for publication: ON TWO APPROXIMATION ALGORITHMS FOR THE CLIQUE PROBLEM

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