𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A randomized algorithm for finding a near-maximum clique and its experimental evaluations

✍ Scribed by Yoshiaki Yamada; Etsuji Tomita; Haruhisa Takahashi

Book ID
104591615
Publisher
John Wiley and Sons
Year
1994
Tongue
English
Weight
441 KB
Volume
25
Category
Article
ISSN
0882-1666

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The so‐called Maximum Clique Problem is one of the most famous NP‐complete problems for which it is difficult to find a solution. Given an indirected graph, we present here a polynomial‐time randomized algorithm RaCLIQUE for finding a near‐maximum clique. While the basic idea of the algorithm comes from Boltzmann machines, it employs no simulated annealing at all and hence it is simple to control its execution. We have confirmed in experiments for several random and nonrandom graphs with up to 400 nodes that very good solutions can be found efficiently compared with the other conventional algorithms.

πŸ“œ SIMILAR VOLUMES

A neural network model for finding a nea
A neural network model for finding a near-maximum clique
✍ Nubuo Funabiki; Yoshiyasu Takefuji; Kuo-Chun Lee πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 397 KB

A parallel algorithm based on the neural network model for finding a near-maximum clique is presented in this paper. A maximum clique of a graph G is a maximum complete subgraph of G where any two vertices are adjacent. The problem of finding a maximum clique is NP-complete. The parallel algorithm r