
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Comparisons of EnergyDescent Optimization Algorithms for Maximum Clique Problems
Nobuo FUNABIKI Seishi NISHIKAWA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E79A
No.4
pp.452460 Publication Date: 1996/04/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: maximum clique, NPcomplete, neural network, algorithm, energydescent opimization,
Full Text: PDF(605.7KB)>>
Summary:
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 wellknown NPcomplete problem. Recently, several polynomial time energydescent 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 energydescent optimization algorithm. Through two types of random graphs, we compare the performance of four promising energydescent 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.

