کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949892 | 1364262 | 2017 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On recognition of threshold tolerance graphs and their complements
ترجمه فارسی عنوان
در شناخت نمودارهای تحمل آستانه و تکمیل آنها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
کلاس های گراف، الگوریتم های شناخت، نمودار تحمل آستانه، نمودارهای کاملا هوشیار، نمودارهای فاصله،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 171-180
نویسندگان
Petr A. Golovach, Pinar Heggernes, Nathan Lindzey, Ross M. McConnell, VinÃcius Fernandes dos Santos, Jeremy P. Spinrad, Jayme Luiz Szwarcfiter,