𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on the approximation of the max clique problem

✍ Scribed by P. Crescenzi; C. Fiorini; R. Silvestri

Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
312 KB
Volume
40
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The max clique problem in classes of str
The max clique problem in classes of string-graphs
✍ M. Middendorf; F. Pfeiffer πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 378 KB

Middendorf, M., F. Pfeiffer, The max clique problem in classes of string-graphs, Discrete Mathematics 108 (1992) 365-372. A string-graph is an intersection graph of a set of curves in the plane. Investigating the complexity of the max clique problem for some classes of string-graphs we obtain NPcomp

On the approximability of clique and rel
On the approximability of clique and related maximization problems
✍ Aravind Srinivasan πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 247 KB

We consider approximations of the form n 1Γ€oΓ°1Þ for the Maximum Clique problem, where n is the number of vertices in the input graph and where the ''oΓ°1Þ'' term goes to zero as n increases. We show that sufficiently strong negative results for such problems, which we call strong inapproximability re