Abdullah Al-Azemi

Advisor: Dr. Anton Betten

Degree Conferred: Summer 2007

After Graduation: Professor, Kuwait University

Website: Not Available

Thesis Title:

Classification Algorithms For Graphs, Digraphs, And Linear Spaces

Abstract:

Combinatorial incidence structures like graphs, digraphs, and linear spaces are defined modulo an isomorphism relation. Typically we are interested in determining complete systems of representatives of the isomorphism classes, in order to test conjectures or to prove existence or non-existence of examples for new theorems. In this thesis, we present classification algorithms for graphs, digraphs, and incidence structures. We discuss both the use of invariants and the use of partition backtracking for solving the isomorphism problems of {0,1}-matrices. After that, we consider the inverse problem of finding all strucutres for a given invariant. This leads to the composition principle for incidence structures and eventually to the computation of all 8,592,194,823 linear spaces on 13 points.