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