ON TWO APPROXIMATION ALGORITHMS FOR THE CLIQUE PROBLEM

DOI10.1142/S0129054193000080MaRDI QIDQ4286115zbMATHFDO

Authors Iain Stewart

Publication date 27 March 1994

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

zbMATH Keywords

complexityapproximation algorithmsgreedy algorithms\(\mathbb{P}\)-completeoptimization 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

(10)

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

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)