An empirical study on the efficiency of the Corneil- Gotleib algorithm for graph isomorphism

Date

10-1988

Degree

Bachelor of Science in Applied Mathematics

College

College of Arts and Sciences (CAS)

Adviser/Committee Chair

Alleli C. Domingo

Abstract

A method for determining the isomorphism of two finite given graphs is presented, called the Corneil-Gotleib algorithm. This method derives a representative graph and from it, a reordered graph. If the representative graph of one graph is identical with the representative graph of the other, then, these graphs are reordered. If the reordering of both graphs are alike, then they are said to be isomorphic. The efficiency of the Corneil-Gotleib algorithm is analyzed empirically, and is compared with the algorithm created by Ullman which also checks for isomorphism. This, aside from the actual clockings gathered, is further aided through the use of the one--way analysis of variance for determining whether the means of these two populations differ significantly from each other. In the final analysis, the Corneil-Gotleib algorithm emerges as the more efficient algorithm. It computes in polynomial time, with t It being the time) increasing proportionally with n In being the order of the graph).

Language

English

Location

UPLB Main Library Special Collections Section (USCS)

Call Number

Thesis

Document Type

Thesis

This document is currently not available here.

Share

COinS