| Article ID: | iaor19932427 |
| Country: | United Kingdom |
| Volume: | 5 |
| Start Page Number: | 69 |
| End Page Number: | 71 |
| Publication Date: | Mar 1992 |
| Journal: | Applied Mathematics Letters |
| Authors: | Codenotti B., Margara L. |
| Keywords: | programming: integer, graphs |
It has been shown that certain NP-complete problems, i.e., TSP, min cut, and graph partitioning, with specific notions of neighborhood, satisfy a simple difference equation. In this paper, the authros extend these results by proving that TSP with some notions of neighborhood satisfy such a difference equation. Furthermore, they derive some structural properties satisfied by the above-mentioned problem.