| Article ID: | iaor19921411 |
| Country: | Netherlands |
| Volume: | 36 |
| Issue: | 2 |
| Start Page Number: | 167 |
| End Page Number: | 170 |
| Publication Date: | Jan 1992 |
| Journal: | Discrete Applied Mathematics |
| Authors: | Murphy Owen J. |
It is shown that the well-known independent set problem remains NP-complete even when restricted to graphs which contain no cycles of length less than