COMING SOON! PQDT Open is getting a new home!

ProQuest Open Access Dissertations & Theses will remain freely available as part of a new and enhanced search experience at

Questions? Please refer to this FAQ.

Dissertation/Thesis Abstract

Isomorphisms in Co-TT Graphs
by Besen, David K., M.S., Colorado State University, 2019, 40; 13812809
Abstract (Summary)

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 + wymin(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.

Indexing (document details)
Advisor: McConnell, Ross
Commitee: Bohm, Anton, Peterson, Chris
School: Colorado State University
Department: Computer Science
School Location: United States -- Colorado
Source: MAI 58/06M(E), Masters Abstracts International
Subjects: Computer science
Keywords: Algorithms, Co-TT graphs, Graph theory, Isomorphism, Threshold tolerance graphs
Publication Number: 13812809
ISBN: 978-1-392-27373-9
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy