Generalizations of comparability graphs
| dc.contributor.author | Xu, Zhisheng, author | |
| dc.contributor.author | McConnell, Ross, advisor | |
| dc.contributor.author | Ortega, Francisco, committee member | |
| dc.contributor.author | Cutler, Harvey, committee member | |
| dc.contributor.author | Hulpke, Alexander, committee member | |
| dc.date.accessioned | 2022-08-29T10:17:00Z | |
| dc.date.available | 2022-08-29T10:17:00Z | |
| dc.date.issued | 2022 | |
| dc.description.abstract | In rational decision-making models, transitivity of preferences is an important principle. In a transitive preference, one who prefers x to y and y to z must prefer x to z. Many preference relations, including total order, weak order, partial order, and semiorder, are transitive. As a preference which is transitive yet not all pairs of elements are comparable, partial orders have been studied extensively. In graph theory, a comparability graph is an undirected graph which connects all comparable elements in a partial order. A transitive orientation is an assignment of direction to every edge so that the resulting directed graph is transitive. A graph is transitive if there is such an assignment. Comparability graphs are a class of graphs where clique, coloring, and many other optimization problems are solved by polynomial algorithms. It also has close connections with other classes of graphs, such as interval graphs, permutation graphs, and perfect graphs. In this dissertation, we define new measures for transitivity to generalize comparability graphs. We introduce the concept of double threshold digraphs together with a parameter λ which we define as our degree of transitivity. We also define another measure of transitivity, β, as the longest directed path such that there is no edge from the first vertex to the last vertex. We present approximation algorithms and parameterized algorithms for optimization problems and demonstrate that they are efficient for "almost-transitive" preferences. | |
| dc.format.medium | born digital | |
| dc.format.medium | doctoral dissertations | |
| dc.identifier | Xu_colostate_0053A_17231.pdf | |
| dc.identifier.uri | https://hdl.handle.net/10217/235671 | |
| dc.language | English | |
| dc.language.iso | eng | |
| dc.publisher | Colorado State University. Libraries | |
| dc.relation.ispartof | 2020- | |
| 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 | comparability graphs | |
| dc.subject | partial orders | |
| dc.subject | approximation algorithms | |
| dc.subject | transitivity | |
| dc.subject | parameterized algorithms | |
| dc.title | Generalizations of comparability 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 | Doctoral | |
| thesis.degree.name | Doctor of Philosophy (Ph.D.) |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Xu_colostate_0053A_17231.pdf
- Size:
- 823.66 KB
- Format:
- Adobe Portable Document Format