Login | Register

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
1MB

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 17:18
Last Modified:08 Dec 2010 15: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

Downloads

Downloads per month over past year

Back to top Back to top