Maximal-Clique Problem Formulation for Common Structure Detection in Many Graphs
Wataru Nakasone, Morikazu Nakamura · 2022
This paper formulates maximal clique problems by extending the definition of an association graph based on edge-isomorphism to extract common multifrequency subgraphs between more than three graphs. As the size of the extended association graph is expected to be huge, we present a new approximation algorithm for solving the maximum clique problem, which replaces the integer programming problem used in previous studies. Furthermore, we propose a parallel processing method for the new algorithm. Experimental results show that the method solves the maximum clique problem faster than the integer programming problem while keeping the quality of the solutions.