✦ LIBER ✦

On the approximability of clique and related maximization problems

✍ Scribed by Aravind Srinivasan

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 247 KB
Volume: 67
Category: Article
ISSN: 0022-0000
DOI: 10.1016/s0022-0000(03)00110-7

No coin nor oath required. For personal study only.

✦ Synopsis

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 results, have interesting consequences for exact computation. A simple sampling method underlies most of our results.

📜 SIMILAR VOLUMES

On approximability of linear ordering an

On approximability of linear ordering and related NP-optimization problems on graphs

✍ Sounaka Mishra; Kripasindhu Sikdar 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 337 KB

We investigate the approximability of minimum and maximum linear ordering problems (MIN-LOP and MAX-LOP) and related feedback set problems such as maximum weight acyclic subdiagraph (MAX-W-SUBDAG), minimum weight feedback arc/vertex set (MIN-W-FAS/ MIN-W-FVS) and a generalization of the latter calle

A note on the approximation of the max c

A note on the approximation of the max clique problem

✍ P. Crescenzi; C. Fiorini; R. Silvestri 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 312 KB

On Approximability of Linear Ordering an

On Approximability of Linear Ordering and Related NP-optimization Problems on Graphs (Extended Abstract)

✍ Sounaka Mishra; Kripasindhu Sikdar 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 297 KB

Edge-maximal triangulated subgraphs and

Edge-maximal triangulated subgraphs and heuristics for the maximum clique problem

✍ Jue Xue 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 855 KB

On the approximability of some maximum s

On the approximability of some maximum spanning tree problems

✍ Giulia Galbiati; Angelo Morzenti; Francesco Maffioli 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 844 KB

We study the approximability of some problems which aim at finding spanning trees in undirected graphs which maximize, rather than minimize, a single objective function representing a form of benefit or usefulness of the tree. We prove that the problem of finding a spanning tree which maximizes the

The maximal clique and colourability of

The maximal clique and colourability of curve contact graphs

✍ Petr Hlineˇný 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 669 KB

## Contact graphs are a special kind of intersection graphs of geometrical objects in which the objects are not allowed to cross but only to touch each other. Contact graphs of simple curves, and line segments as a special case, in the plane are considered. The curve contact representations are st