Comparisons of energy-descent optimization algorithms for maximum clique problems

Nobuo Funabiki, Seishi Nishikawa

Research output: Contribution to journalArticlepeer-review

23 Citations (Scopus)


A clique of a graph G (V, E) is a subset of V such that every pair of vertices is connected by an edge in E. Finding a maximum clique of an arbitrary graph is a well-known NP-complete problem. Recently, several polynomial time "energy-descent optimization" algorithms have been proposed for approximating the maximum clique problem, where they seek a solution by minimizing the energy function representing the constraints and the goal function. In this paper, we propose the binary neural network as an efficient synchronous energy-descent optimization algorithm. Through two types of random graphs, we compare the performance of four promising energy-descent optimization algorithms. The simulation results show that "RaCLIQUE," the modified Boltzmann machine algorithm, is the best asynchronous algorithm for random graphs, while the binary neural network is the best one for k random cliques graphs.

Original languageEnglish
Pages (from-to)452-459
Number of pages8
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number4
Publication statusPublished - Jan 1 1996
Externally publishedYes


  • Algorithm
  • Energy-descent optimization
  • Maximum clique
  • Neural network
  • Np-complete

ASJC Scopus subject areas

  • Signal Processing
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering
  • Applied Mathematics


Dive into the research topics of 'Comparisons of energy-descent optimization algorithms for maximum clique problems'. Together they form a unique fingerprint.

Cite this