Department of Computer Science
Permanent URI for this community
This digital collection contains theses and dissertations from the Department of Computer Science.
Browse
Browsing Department of Computer Science by Subject "algorithms"
Now showing 1 - 3 of 3
Results Per Page
Sort Options
Item Open Access A parametric classification of directed acyclic graphs(Colorado State University. Libraries, 2017) Chaturvedi, Mmanu, author; McConnell, Ross M., advisor; Kirby, Michael J., committee member; Rajopadhye, Sanjay V., committee member; Oprea, Iuliana, committee memberWe consider four NP-hard optimization problems on directed acyclic graphs (DAGs), namely, max clique, min coloring, max independent set and min clique cover. It is well-known that these four problems can be solved in polynomial time on transitive DAGs. It is also known that there can be no polynomial O(n1-ϵ)-approximation algorithms for these problems on the general class of DAGs unless P = NP. We propose a new parameter, β, as a measure of departure from transitivity for DAGs. We define β to be the number of vertices in a longest path in a DAG such that there is no edge from the first to the last vertex of the path, and 2 if the graph is transitive. Different values of β define a hierarchy of classes of DAGs, starting with the class of transitive DAGs. We give a polynomial time algorithm for finding a max clique when β is bounded by a fixed constant. The algorithm is exponential in β, but we also give a polynomial β-approximation algorithm. We prove that the other three decision problems are NP-hard even for β ≥ 4 and give polynomial algorithms with approximation bounds of β or better in each case. Furthermore, generalizing the definition of quasi-transitivity introduced by Ghouilà-Houri, we define β-quasi-transitivity and prove a more generalized version their theorem relating quasi-transitive orientation and transitive orientation.Item Open Access Faster graph algorithms via switching classes(Colorado State University. Libraries, 2012) Lindzey, Nathan, author; McConnell, Ross, advisor; Bohm, Wim, committee member; Penttila, Tim, committee memberThe runtime of an algorithm is intimately related to how an instance is represented. Recall that the runtimes of the first generation of graph algorithms were expressed as functions of n := |V|. This analysis was natural since at this time graphs were represented in n2 space via their adjacency matrix. It was soon noticed that if m := |E| = o(n2), then a variety of graph algorithms could be sped-up by computing the adjacency-list from the adjacency matrix, then running the algorithm on the more efficient adjacency-list representation. This motivated the introduction of m to the runtime of graph algorithms and it is now customary in algorithm design to assume that a graph instance is given in the form of its adjacency-list. For instance, a graph algorithm is not considered to run in linear time unless it runs in O(n + m) time. An O(n2) bound is not considered linear, even though the two bounds are the same in the worst case. Let m͂ be the size of the minimum representative of a graph G's switching class (w.r.t. to some switching operation). It is shown that better bounds for several classical graph algorithms can be obtained by modifying them so that their running time is a function of n+m͂ rather than of n+m. This is significant because m͂ is O(m) but m is not O(m͂). This is accomplished by first computing the so-called partially complemented adjacency list (pc-list) from an adjacency list, then designing an algorithm that is amenable to the more efficient pc-list representation. The pc-list data-structure is generalization of the adjacency list that has a natural correspondence to switching classes. Using this approach, better bounds are obtained for bipartite maximum matching, graph diameter, and vertex-weighted all-pairs shortest path.Item Open Access Isomorphisms in co-TT graphs(Colorado State University. Libraries, 2019) Besen, David K., author; McConnell, Ross, advisor; Bohm, Wim, committee member; Peterson, Chris, committee memberA threshold tolerance graph is a graph where each vertex v is assigned a weight wv and a tolerance tv, and there is an edge between two vertices vx and vy if and only if wx + wy ≥ min(tx,ty). A co-TT graph is the complement of a threshold tolerance graph. Recognition of these graphs can be done in O(n2) time; however no polynomial-time algorithm to identify isomorphisms between pairs of TT or co-TT graphs was previously known. We give an algorithm to identify these isomorphisms, which takes O(n2) time.