The problem of vertex coloring holds an important place in engineering as it models situations in which a number of shared resources must be minimized and distributed across the sub-components of a system. The objective is to ensure a valid and cost effective implementation of the overall system. The problem surfaces in a great number of applications, many of which fall within the area of digital systems design. However, despite its wide range of applications, vertex coloring remains one of the most complex optimization problems known and to this day no efficient method has been shown to provide optimal answers in all instances of the general case. / This dissertation explores characteristics of optimality of vertex colorings, bounds on the chromatic number and coloring heuristics. The first few characteristics are based around the fundamental and residual nodes of an optimal coloring. An examination of the subset of fundamental nodes will reveal necessary subgraph properties for an optimal coloring and its graph; one of which is based on Kempe chains. In turn, this leads to a bound relating the chromatic number and the number of odd cycles in a graph. / Subsequently, a continuous variable formulation of the vertex coloring problem is presented along with an analysis of its solution space. The characterization of the space illustrates the problem's complexity and the nature of its local minima relates to the Gallai-Roy theorem. The results given will have algorithmic significance since their proofs are constructive. / The WWI pair of vertex coloring heuristics is then disclosed. The algorithms are based on successive compressions of pairs of non-adjacent nodes each reducing the problem instance by one node until a complete graph is obtained. The criteria for selecting pairs of nodes concentrate on the affinity and conflict values calculated from structural properties of the graphs. The heuristics are justified by upper bounds on the chromatic number and approximation arguments. It is demonstrated that some compressions preserve the chromatic number or the maximal clique size of a graph, thus resulting into some identifiably optimal selections by the algorithms. Ultimately, this leads to the characterization of a class of perfect graphs. Finally, a set of benchmarks for the WWI algorithms on random graphs and k-colorable random graphs is given and favorable comparisons are offered with existing algorithms.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.40193 |
| Date | January 1996 |
| Creators | Masson, Eric |
| Contributors | Agarwal, Vinod K. (advisor), Bhatt, Pramod C. P. (advisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Doctor of Philosophy (Department of Electrical Engineering.) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | alephsysno: 001486275, proquestno: NN12433, Theses scanned by UMI/ProQuest. |
Page generated in 0.0077 seconds