HEWN: A polynomial algorithm for CLIQUE problem. This paper presents an algorithm with polynomial time complexity for CLIQUE problem. A Hierarchical Edge-Weighted Network (HEWN) which is equivalent to the corresponding Maximum Complete Subgraph Tree (MCST) is proposed. In the network, the arrangement of vertices is hierarchical and each edge is attached by a guiding matrix that reflects those paths in MCST. By decomposing-rolling-composing operation, a consistent HEWN will finally be built and hence the size of maximal clique is found. It is proved that HEWN is equivalent to the MCST and the time complexity of building HEWN is polynomial. The implementation results coincide with the proofs.

This software is also peer reviewed by journal TOMS.