Isomorphisms in co-TT graphs
| dc.contributor.author | Besen, David K., author | |
| dc.contributor.author | McConnell, Ross, advisor | |
| dc.contributor.author | Bohm, Wim, committee member | |
| dc.contributor.author | Peterson, Chris, committee member | |
| dc.date.accessioned | 2019-06-14T17:06:26Z | |
| dc.date.available | 2019-06-14T17:06:26Z | |
| dc.date.issued | 2019 | |
| dc.description.abstract | A 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. | |
| dc.format.medium | born digital | |
| dc.format.medium | masters theses | |
| dc.identifier | Besen_colostate_0053N_15385.pdf | |
| dc.identifier.uri | https://hdl.handle.net/10217/195343 | |
| 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 | Co-TT graphs | |
| dc.subject | isomorphism | |
| dc.subject | algorithms | |
| dc.subject | threshold tolerance graphs | |
| dc.subject | graph theory | |
| dc.title | Isomorphisms in co-TT 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:
- Besen_colostate_0053N_15385.pdf
- Size:
- 285.56 KB
- Format:
- Adobe Portable Document Format