|کد مقاله||کد نشریه||سال انتشار||مقاله انگلیسی||ترجمه فارسی||نسخه تمام متن|
|4949892||1364262||2017||10 صفحه PDF||سفارش دهید||دانلود کنید|
A graph G=(V,E) is a threshold tolerance graph if each vertex vâV can be assigned a weight wv and a tolerance tv such that two vertices x,yâV are adjacent if 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) runtime. We give an 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.
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 171-180