کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
482195 | 1446183 | 2008 | 11 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Some observations on maximum weight stable sets in certain P5-free graphs Some observations on maximum weight stable sets in certain P5-free graphs](/preview/png/482195.png)
The maximum weight stable set problem (MWS) is the weighted version of the maximum stable set problem (MS), which is NP-hard. The class of P5-free graphs – i.e., graphs with no induced path of five vertices – is the unique minimal class, defined by forbidding a single connected subgraph, for which the computational complexity of MS is an open question. At the same time, it is known that MS can be efficiently solved for (P5,F)(P5,F)-free graphs, where F is any graph of five vertices different to a C5. In this paper we introduce some observations on P5-free graphs, and apply them to introduce certain subclasses of such graphs for which one can efficiently solve MWS. That extends or improves some known results, and implies – together with other known results – that MWS can be efficiently solved for (P5,F)(P5,F)-free graphs where F is any graph of five vertices different to a C5.
Journal: European Journal of Operational Research - Volume 184, Issue 3, 1 February 2008, Pages 849–859