Breadcrumb

 
 

Maximum cliques and vertex colorings in random and k-partite graphs

Title:

Maximum cliques and vertex colorings in random and k-partite graphs

Hughes, Thomas (2000) Maximum cliques and vertex colorings in random and k-partite graphs. Other thesis, Concordia University.

[img]
Preview
PDF
1905Kb

Abstract

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)
Authors:Hughes, Thomas
Pagination:vi, 71 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:Major reports (M.Comp.Sc.)
Program:Computer Science and Software Engineering
Date:2000
Thesis Supervisor(s):Lam, Clement
ID Code:1290
Deposited By:Concordia University Libraries
Deposited On:27 Aug 2009 13:18
Last Modified:08 Dec 2010 10:19
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Document Downloads

More statistics for this item...

Concordia University - Footer