Toronto Metropolitan University
Browse
Patel_Sonal.pdf (977.24 kB)

Clique Listing Algorithms and Characteristics of Cliques in Random Graphics

Download (977.24 kB)
thesis
posted on 2021-05-23, 15:22 authored 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

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC