Patel_Sonal.pdf (977.24 kB)

Clique Listing Algorithms and Characteristics of Cliques in Random Graphics

Download (977.24 kB)
thesis
posted on 23.05.2021, 15:22 by Sonal Patel
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.

History

Language

eng

Degree

Master of Science

Program

Computer Science

Granting Institution

Ryerson University

LAC Thesis Type

Thesis

Usage metrics

Computer Science (Theses)

Exports