Local Properties of Some NP-Complete Problems
| Title | Local Properties of Some NP-Complete Problems |
| Publication Type | Technical Report |
| Year of Publication | 1992 |
| Authors | Codenotti, B., & Margara L. |
| Other Numbers | 726 |
| Abstract | 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, we extend these results by proving that TSP with 2-change, 2+3-new-change, and 3-new-change notions of neighborhood satisfy such a difference equation, and we derive some properties of local search when performed with the above definitions of neighborhood. |
| URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-92-021.pdf |
| Bibliographic Notes | ICSI Technical Report TR-92-021 |
| Abbreviated Authors | B. Codenotti and L. Margara |
| ICSI Publication Type | Technical Report |