Isomorphisms in co-TT graphs - Besen, David K., author; McConnell, Ross, advisor; Bohm, Wim, committee member; Peterson, Chris, committee member (Colorado State University. Libraries, 2019)
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.
Keywords: Co-TT graphs; isomorphism; algorithms; threshold tolerance graphs; graph theory