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
Source Type: DISSERTATION
Subjects: Computer science
Keywords: Algorithms, Co-TT graphs, Graph theory, Isomorphism, Threshold tolerance graphs
Publication Number: 13812809
ISBN: 978-1-392-27373-9
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy
ProQuest