A note on the approximation of the MAX CLIQUE problem

DOI10.1016/S0020-0190(05)80002-XzbMath0751.68027MaRDI QIDQ1183423

S. Singh

Publication date: 28 June 1992

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

approximation preserving reducibilityclass MAX NPMAX CLIQUE problem

Mathematics Subject Classification ID

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

Related Items

Extended and discretized formulations for the maximum clique problem ⋮ Finding optimal subgraphs by local search ⋮ On the complexity of the shortest-path broadcast problem ⋮ Approximate solution of NP optimization problems ⋮ A note on the descriptive complexity of maximization problems ⋮ Maximum cut-clique problem: ILS heuristics and a data analysis application ⋮ The maximum clique problem ⋮ Modelling competitive Hopfield networks for the maximum clique problem

Cites Work

• Logical definability of NP optimization problems
• The Complexity of Near-Optimal Graph Coloring
• On the complexity of approximating the independent set problem
• Unnamed Item
• Unnamed Item
• Unnamed Item