Search

This thesis examines the devices employed by various algorithms to search for maximal complete subgraphs in graphs. Also known as cliques, in Chapter 1 these subgraphs are seen to play an important role in graph theory, information retrieval, Sociometry, logic design, and computational complexity. The enumeration of cliques using the Harary-Rcss, Bonner, Peay, and Bron-Kerbosch algorithms is discussed in Chapter 2. The Reduced Redundancy algorithm is introduced, and the performance of the five procedures is assessed using an alternative approach to empirical testing. Each of the algorithms is shown to generate a "derivation tree" for a given graph whose size can be used as a measure of its efficiency. In Chapter 3, the possibility of exploiting vertex similarity is examined with a view to reducing the size of the derivation tree. As a consequence, algorithms are proposed for finding non-similar cliques. The concept of "complete subgraph equivalence" of vertices is introduced to develop a means for expressing the cliques of a graph as the Cartesian product of vertex subsets. An algorithm for detecting the existence of a clique of order k in a certain class of k-partite graphs in polynomial time is proposed in Chapter 4. This class consists of all graphs reducible by the algorithm to k-partite graphs having at most two vertices per block of degree greater than 0. This algorithm is shown to provide an efficient heuristic which can be used in a procedure for determining whether a well-formed formula is a tautology. The thesis is concluded with an empirical analysis of the techniques employed by the enumeration algorithms of Chapter 2. In addition, the efficiency of the Clique Detection algorithm is compared with that of the Reduced Redundancy algorithm.

The purpose of this thesis is to investigate the graph isomorphism problem for a special class of graphs. Each graph is characterized by its edge set, and a subgroup of its automorphism group, called the colour group. In particular, a simple, efficient algorithm for determining whether two graphs are isomorphic if at least one is a member of the class is developed. Chapter 1 provides some basic definitions and lemmas required in the text. The concepts of reducibility and reducible bipartite graphs are introduced, and the properties of the colour groups of such graphs are investigated. Chapter 2 establishes some results concerning the existence of reducible graphs. Conditions based on the existence of vertices with prescribed properties are shown to provide sufficient conditions for a graph to be reducible. In the special case of trees they are shown to be both necessary and sufficient. Necessary conditions for the reducibility of graphs, based on their radius and diameter are also established. Chapter 3 describes an algorithm for determining whether a graph is completely reducible, which is applied to a test for isomorphism. An investigation of the speed of this algorithm is made and its efficiency is compared with an algorithm of D. Corneil [5], which this author considers the best for arbitrary graphs in the current literature.