Clique Listing Algorithms and Characteristics of Cliques in Random Graphics

In this thesis we address three main problems in clique detection in the area of Graph Theory. i) Most of current methods for clique detection are time consuming (can take exponential time to the size of input graph), so there is a practical limit on size of input graph. In this thesis we propose three different methods for estimating the number of cliques. We examine these methods for various graphs and conclude that they efficiently find the number of cliques within 5% error typically. ii) We compare various versions of the Bron-Kerbosch (BK) clique listing algorithm to discover a method of combining the best features of different versions. We test our new versions of BK for various inputs. iii) We study the characteristics of cliques in random graphs as a function of size and density.