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.
|Advisor:||McConnell, Ross M.|
|Commitee:||Kirby, Michael J., Oprea, Iuliana, Rajopadhye, Sanjay V.|
|School:||Colorado State University|
|School Location:||United States -- Colorado|
|Source:||MAI 57/01M(E), Masters Abstracts International|
|Keywords:||Algorithms, Graph theory, Np-hard optimization|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be