Repository logo
 

Isomorphisms in co-TT graphs

Date

2019

Authors

Besen, David K., author
McConnell, Ross, advisor
Bohm, Wim, committee member
Peterson, Chris, committee member

Journal Title

Journal ISSN

Volume Title

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.

Description

Rights Access

Subject

Co-TT graphs
isomorphism
algorithms
threshold tolerance graphs
graph theory

Citation

Associated Publications