| Article ID: | iaor20021927 |
| Country: | Japan |
| Volume: | 44 |
| Issue: | 2 |
| Start Page Number: | 194 |
| End Page Number: | 204 |
| Publication Date: | Jun 2001 |
| Journal: | Journal of the Operations Research Society of Japan |
| Authors: | Tamura Akihisa, Nakamura Daishin |
| Keywords: | optimization |
Minty, Sbihi, and Lovász and Plummer have proposed polynomial time algorithms finding a maximum cardinality stable set of a claw-free graph. However, it has been believed that Minty's algorithm is the unique polynomial time algorithm finding a maximum weight stable set of a claw-free graph up to date. The authors show that Minty's algorithm for the weighted version fails for some special cases, and give modifications to overcome it.