SOLVING THE MAXIMUM CLIQUE PROBLEM USING INTELLIGENT WATER DROPS ALGORITHM
Ahmad T. Al‐Taani, Mohammad K. Nemrawi · 2012
The MCP is a classical NP-hard optimization problem. It has many practical applications in different domains such as project selection, classification, fault tolerance, coding, computer vision, economics, information retrieval and signal transmission. Given an undirected graph G = (V, E) such that V is a set of vertices and E is a set of edges in graph G, a clique C is a complete sub-graph of G, C is complete if all its vertices are pair wise adjacent. Two vertices are said to be adjacent if they are connected by an edge. A clique called partial clique if all of its vertices’ are subset of larger clique; otherwise it is a maximal clique. The goal of the maximum clique problem is to find a clique of maximum size (which contains the maximum number of vertices). The maximum clique is one of the maximal cliques in the graph and cannot be a partial clique [1]. IWDs algorithm operates like paths that the river follows in the nature, these paths are full of twist and turns. In the ideal form, the water drops in river would use the gravitational force of the earth to follow a straight path to reach their destination, which is the shortest path from the source to the destination. However, water drops can't flow in such ideal path; that is because there are different kinds of obstacles and barriers in their way to the destination that prevent the river from going on straight line and make its' real path full of twists and turns. On the other hand, the water drops always try to change their environment in order to make their real path as ideal as possible. In fact, this constructed path seems to be optimum in terms of distance from the destination and the constraints of the environment. One of the most important features that enable nature water drops to change their environment to find optimum path is the velocity that it flows. This feature enable water drop to carry an amount of soil while it is moving from one place to another. Hence, based on the observation of water drop behavior and features, IWDs algorithm had been developed. In the new IWDs algorithm, the water drop possesses SOLVING THE MAXIMUM CLIQUE PROBLEM USING INTELLIGENT WATER DROPS ALGORITHM