| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4651878 | Electronic Notes in Discrete Mathematics | 2015 | 7 Pages |
Abstract
We consider the Maximum Independent Set (MIS) problem, which is known to be NP-hard in general, in subclasses of Si,j,k-free graphs, where Si,j,k is the graph consisting of three induced paths of lengths i,j,k with a common initial vertex. We revise the complexity of the problem. Then by two general approaches, augmenting graph and α-redundant vertex, some graph classes, for which we have polynomial solutions, are obtained.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
