A parametric classification of directed acyclic graphs
| dc.contributor.author | Chaturvedi, Mmanu, author | |
| dc.contributor.author | McConnell, Ross M., advisor | |
| dc.contributor.author | Kirby, Michael J., committee member | |
| dc.contributor.author | Rajopadhye, Sanjay V., committee member | |
| dc.contributor.author | Oprea, Iuliana, committee member | |
| dc.date.accessioned | 2017-09-14T16:04:44Z | |
| dc.date.available | 2017-09-14T16:04:44Z | |
| dc.date.issued | 2017 | |
| dc.description.abstract | 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. | |
| dc.format.medium | born digital | |
| dc.format.medium | masters theses | |
| dc.identifier | Chaturvedi_colostate_0053N_14288.pdf | |
| dc.identifier.uri | https://hdl.handle.net/10217/183921 | |
| dc.language | English | |
| dc.language.iso | eng | |
| dc.publisher | Colorado State University. Libraries | |
| dc.relation.ispartof | 2000-2019 | |
| dc.rights | Copyright 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. | |
| dc.subject | graph theory | |
| dc.subject | algorithms | |
| dc.title | A parametric classification of directed acyclic graphs | |
| dc.type | Text | |
| dcterms.rights.dpla | This Item is protected by copyright and/or related rights (https://rightsstatements.org/vocab/InC/1.0/). You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s). | |
| thesis.degree.discipline | Computer Science | |
| thesis.degree.grantor | Colorado State University | |
| thesis.degree.level | Masters | |
| thesis.degree.name | Master of Science (M.S.) |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Chaturvedi_colostate_0053N_14288.pdf
- Size:
- 501.03 KB
- Format:
- Adobe Portable Document Format