کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647002 | 1342321 | 2016 | 12 صفحه PDF | دانلود رایگان |
The method of augmenting graphs is a general approach to solve the Maximum Independent Set problem. Our objective is to employ this approach to develop polynomial-time algorithms for some so-called Maximum Set problems, i.e. problems which can be stated as follows. Given a (simple) graph GG, find a maximum vertex subset SS of GG such that the subgraph induced by SS satisfies a given property ΠΠ. Such problems were shown to be NP-hard in general if the properties considered are non-trivial and hereditary Lewis and Yannakakis (1980) and Yannakakis (1978). In this paper, using the augmenting graph technique, we describe a graph class, in which some problems can be solved in polynomial time. We also prove the NP-hardness of some Maximum Set problems where the considered properties are not hereditary.
Journal: Discrete Mathematics - Volume 339, Issue 8, 6 August 2016, Pages 2186–2197