Local Properties of Some NP-Complete Problems

TitleLocal Properties of Some NP-Complete Problems
Publication TypeTechnical Report
Year of Publication1992
AuthorsCodenotti, B., & Margara L.
Other Numbers726

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.

Bibliographic Notes

ICSI Technical Report TR-92-021

Abbreviated Authors

B. Codenotti and L. Margara

ICSI Publication Type

Technical Report