کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418996 | 681731 | 2015 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Counting independent sets in a tolerance graph
ترجمه فارسی عنوان
شمارش مجموعه های مستقل در یک گراف تحمل
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار تحمل مجموعه مستقل، مجموعه های حداکثر مستقل، مستقل کامل سلطه غالب، شمارش مشکل
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Counting independent sets is a #P-complete problem for general graphs but solvable in polynomial time for interval and permutation graphs. This paper develops some polynomial time algorithms for counting independent sets, maximal independent sets, and independent perfect dominating sets in a tolerance graph, which is a common generalization of interval and permutation graphs. No algorithm for solving those problems for tolerance graphs is currently available.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 181, 30 January 2015, Pages 174–184
Journal: Discrete Applied Mathematics - Volume 181, 30 January 2015, Pages 174–184
نویسندگان
Min-Sheng Lin, Sheng-Huang Su,