کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4949902 1364262 2017 9 صفحه PDF سفارش دهید دانلود کنید
عنوان انگلیسی مقاله ISI
A sufficient condition to extend polynomial results for the Maximum Independent Set Problem
ترجمه فارسی عنوان
یک شرط کافی برای تکثیر نتایج چندجملهای برای مسئله مجموعه حداکثر مستقل
کلمات کلیدی
حداکثر مشکل مجموعه مستقل، الگوریتم چندجمله ای،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

The Maximum Weight Independent Set Problem (WIS) is a well-known NP-hard problem. A popular way to study WIS is to detect graph classes for which WIS can be solved in polynomial time, with particular reference to hereditary graph classes (i.e., defined by a hereditary graph property), or equivalently to F-free graphs for a given graph family F (i.e., graphs which are F-free for all F∈F).A tool to extend the results which show that for given hereditary graph classes the WIS problem can be solved in polynomial time is given by the following easy proposition: For any graph family F, if WIS can be solved for F-free graphs in polynomial time, then WIS can be solved for K1+F-free graphs (i.e., graphs which are K1+F-free for all F∈F) in polynomial time.The main result of this paper is the following: A sufficient condition to extend the above proposition to K2+F-free graphs, and more generally to lK2+F-free graphs for any constant l (i.e., graphs which are lK2+F-free for all F∈F), is that F-free graphs are m-plausible for a constant m, i.e., that for any F-free graph G the family of those maximal independent sets I of G such that every vertex of G not in I has more than m neighbors in I can be computed in polynomial time. In this context a section is devoted to show that (for instance) chordal graphs are m-plausible for a constant m.The proof of the main result is based on the idea/algorithm introduced by Farber to prove that every 2K2-free graph has O(n2) maximal independent sets (Farber, 1989), which directly leads to a polynomial time algorithm to solve WIS for 2K2-free graphs through a dynamic programming approach, and on some extensions of that idea/algorithm.

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