کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4949892 1364262 2017 10 صفحه PDF ندارد دانلود کنید
عنوان انگلیسی مقاله
On recognition of threshold tolerance graphs and their complements
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On recognition of threshold tolerance graphs and their complements
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 171-180
نویسندگان
, , , , , , ,