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. [Graduate Projects (Non-thesis)] (Unpublished)

[thumbnail of MQ59327.pdf]
Preview
Text (application/pdf)
MQ59327.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 > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Graduate Projects (Non-thesis)
Authors:Hughes, Thomas
Pagination:vi, 71 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science
Department (as was):Department of Computer Science
Date:2000
Thesis Supervisor(s):Lam, Clement
Identification Number:QA 76 M26+ 2000 no.15
ID Code:1290
Deposited By: Concordia University Library
Deposited On:27 Aug 2009 17:18
Last Modified:20 Oct 2022 20:44
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 per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top