This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
en:mcp [2012/08/03 16:54] – dangducc | en:mcp [2012/08/10 04:00] (current) – dangducc | ||
---|---|---|---|
Line 8: | Line 8: | ||
=== New approach === | === New approach === | ||
- | Subgraph Extraction Approach (SEA) for Solving | + | Subgraph Extraction Approach (SEA) for solving |
Our new idea is follow: the extraction process will not only be influenced by the original graph but also by an order of vertices, this eventually accelerates the extraction. Therefore, if there exists an order of vertices which return the maximum clique of the original graph after the extraction, the MCP can be seen as permutation problem and can be solved using evolutionary algorithms (EA). Particularly for genetic algorithm, this method actually removes the need of repair steps after each crossover operator in genetic algorithm designs for MCP using binary representations. | Our new idea is follow: the extraction process will not only be influenced by the original graph but also by an order of vertices, this eventually accelerates the extraction. Therefore, if there exists an order of vertices which return the maximum clique of the original graph after the extraction, the MCP can be seen as permutation problem and can be solved using evolutionary algorithms (EA). Particularly for genetic algorithm, this method actually removes the need of repair steps after each crossover operator in genetic algorithm designs for MCP using binary representations. | ||
Line 20: | Line 20: | ||
[2] D-C. Dang and A. Moukrim. Subgraph extraction and memetic algorithm for the maximum clique problem. IJCCI (ICEC) 2010, p77-84, 2010. \\ | [2] D-C. Dang and A. Moukrim. Subgraph extraction and memetic algorithm for the maximum clique problem. IJCCI (ICEC) 2010, p77-84, 2010. \\ | ||
[3] J. Xue. Edge-maximal triangulated subgraphs and heuristics for the maximum clique problem. Network, 24: | [3] J. Xue. Edge-maximal triangulated subgraphs and heuristics for the maximum clique problem. Network, 24: | ||
- | [4] D-C. Dang and A. Moukrim. Subgraph extraction and hybrid metaheuristics for the maximum clique problem. | + | [4] D-C. Dang and A. Moukrim. Subgraph extraction and hybrid metaheuristics for the maximum clique problem. |