UMR CNRS 7253

Site Tools

en:mcp

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision		Previous revision
Last revisionBoth sides next revision
en:mcp [2012/08/03 16:10] – created moukrimen:mcp [2012/08/03 18:06] – dangducc
Line 8: Line 8:
 === New approach === === New approach ===
  
-Subgraph Extraction Approach (SEA) for Solving MCP consists of first extracting a particular subgraph from the original one, then finding the maximum clique in this subgraph. Particular subgraphs are chosen such that the MCP can be solved in polynomial time. This approach was early developed in [1, 3] with triangulated subgraphs. The authors proposed also associated heuristic approaches but these algorithms had never been tested on recent MCP benchmarks like the DIMACS one.+Subgraph Extraction Approach (SEA) for solving MCP consists of first extracting a particular subgraph from the original one, then finding the maximum clique in this subgraph. Particular subgraphs are chosen such that the MCP can be solved in polynomial time. This approach was early developed in [1, 3] with triangulated subgraphs. The authors proposed also associated heuristic approaches but these algorithms had never been tested on recent MCP benchmarks like the DIMACS one.
  
 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 18: Line 18:
  
 [1] E. Balas and C. Yu. Finding a maximum clique in an arbitary graph. SIAM Journal of Computing, 15:1054–1068, 1986. \\ [1] E. Balas and C. Yu. Finding a maximum clique in an arbitary graph. SIAM Journal of Computing, 15:1054–1068, 1986. \\
-[2] D-C. Dang and A. Moukrim. Subgraph extraction and memetic algorithm for the maximul 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:109–120, 1994. \\ [3] J. Xue. Edge-maximal triangulated subgraphs and heuristics for the maximum clique problem. Network, 24:109–120, 1994. \\
 [4] D-C. Dang and A. Moukrim. Subgraph extraction and hybrid metaheuristics for the maximum clique problem. //Under revision// [4] D-C. Dang and A. Moukrim. Subgraph extraction and hybrid metaheuristics for the maximum clique problem. //Under revision//

Page Tools

User Tools

en/mcp.txt · Last modified: 2012/08/10 04:00 by dangducc
Mentions légales