Dissertation/Thesis Abstract

A Parametric Classification of Directed Acyclic Graphs
by Chaturvedi, Mmanu, M.S., Colorado State University, 2017, 45; 10599253
Abstract (Summary)

We 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.

Indexing (document details)
Advisor: McConnell, Ross M.
Commitee: Kirby, Michael J., Oprea, Iuliana, Rajopadhye, Sanjay V.
School: Colorado State University
Department: Computer Science
School Location: United States -- Colorado
Source: MAI 57/01M(E), Masters Abstracts International
Source Type: DISSERTATION
Subjects: Computer science
Keywords: Algorithms, Graph theory, Np-hard optimization
Publication Number: 10599253
ISBN: 978-0-355-29565-8
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy
ProQuest