| Article ID: | iaor19962229 |
| Country: | Japan |
| Volume: | J79-D-I |
| Issue: | 1 |
| Start Page Number: | 1 |
| End Page Number: | 8 |
| Publication Date: | Jan 1996 |
| Journal: | Transactions of the Institute of Electronics, Information and Communication Engineers |
| Authors: | Tomita Etsuji, Imamatsu Kenichi, Kohata Yasuhiro, Wakatsuki Mitsuo |
| Keywords: | optimization, graphs |
The authors present a simple and efficient branch and bound recursive algorithm for finding a maximum clique of an undirected graph. The present approach applies successively a pruning method based on greedy coloring following by suitable arrangement for the vertices in consideration. The algorithm reduces the number of search tree nodes effectively and hence runs fast. It is experimentally confirmed to run faster for a number of random graphs with up to 600 vertices and others than the several algorithms which have been appeared in the literature. [In Japanese.]