This paper was written as an assignment of the class ‘Trabalho de Integração I’ that aimed to apply interdisciplinary knowledge in the elaboration of a research project. [Paper in Portuguese]

Abstract: Finding situations where polynomial time algorithms are able to find good solutions for NP-Hard problems is of great practical interest, in fact, verifying this enhancement on complex networks unfolds several possibilities of research, applications, and improvements on a diverse number of fields. Thus, this paper seeks to examine the advantage of exploring the power law distribution of complex networks using greedy algorithms for finding approximate solutions for the Maximum Clique problem.

View PDF