Hughes, Thomas (2000) Maximum cliques and vertex colorings in random and k-partite graphs. Other thesis, Concordia University.
In this project we search for maximum cliques in some random graphs and random k-partite graphs, using either the greedy coloring algorithm or the Dsatur coloring algorithm as bounding functions. We compare the efficiency of the algorithms by looking at the sizes of the resulting state space trees, as well as the number of colors required by the respective coloring algorithms. Finally, we implement a bichromatic interchange algorithm in an attempt to improve the coloring algorithms.
|Divisions:||Concordia University > Faculty of Engineering and Computer Science > Computer Science and Software Engineering|
|Item Type:||Thesis (Other)|
|Pagination:||vi, 71 leaves : ill. ; 29 cm.|
|Degree Name:||Major reports (M.Comp.Sc.)|
|Program:||Computer Science and Software Engineering|
|Thesis Supervisor(s):||Lam, Clement|
|Deposited By:||Concordia University Libraries|
|Deposited On:||27 Aug 2009 13:18|
|Last Modified:||08 Dec 2010 10:19|
Repository Staff Only: item control page