کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4949902 1364262 2017 9 صفحه PDF ندارد دانلود کنید
عنوان انگلیسی مقاله
A sufficient condition to extend polynomial results for the Maximum Independent Set Problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
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
نویسندگان
,