文摘
A graph G=(V,E)G=(V,E) is a threshold tolerance graph if each vertex v∈Vv∈V can be assigned a weight wvwv and a tolerance tvtv such that two vertices x,y∈Vx,y∈V are adjacent if wx+wy≥min(tx,ty)wx+wy≥min(tx,ty). Currently, the most efficient recognition algorithm for threshold tolerance graphs is the algorithm of Monma, Reed, and Trotter which has an O(n4)O(n4) runtime. We give an O(n2)O(n2) algorithm for recognizing threshold tolerance and their complements, the co-threshold tolerance (co-TT) graphs, resolving an open question of Golumbic, Weingarten, and Limouzy.