Manchanda, Saksham, authorMcConnell, Ross, advisorRay, Indrakshi, advisorHulpke, Alexander, committee member2016-08-182016-08-182016http://hdl.handle.net/10217/176622In the general case, in a simple, undirected graph, the problems of finding the largest clique, minimum colouring, maximum independent set and minimum vertex cover are NP-hard. But, there exists some families of graphs, called perfect graphs, where these problems become tractable. One particular class of perfect graphs are the the underlying undirected graphs of transitive digraphs- called comparability graphs. We define a new parameter β to approximate the intransitivity of a given graph. We also use β to give a measure of complexity of finding the largest clique. As β gets worse, the complexity of finding the largest clique quickly grows to exponential times. We also give approximation algorithms that scale with β for all our NP-hard problems. The β measure of a graph can be computed in O(mn), therefore, β can be considered a measure of how tractable these problems are in a graph.born digitalmasters thesesengCopyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see https://libguides.colostate.edu/copyright.beta measureNP completeperfect graphsgraph theoryapproximation algorithmsparametrized algorithmsText