An Efficient Algorithm for Enumerating Pseudo Cliques

摘要: The problem of finding dense structures in a given graph is quite basic informatics including data mining and engineering. Clique popular model to represent structures, widely used because its simplicity ease handling. Pseudo cliques are natural extension which subgraphs obtained by removing small number edges from cliques. We here define pseudo clique subgraph such that the ratio compared with same vertices no less than threshold value. In this paper, we address enumerating all for first show it seems be difficult obtain polynomial time algorithms using straightforward divide conquer approaches. Then, propose time, delay precise, algorithm based on reverse search. efficiency our practice computational experiments.