Publication Details
Title: Local Properties of Some NP-Complete Problems
Author: B. Codenotti and L. Margara
Group: ICSI Technical Reports
Date: April 1992
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-92-021.pdf
Overview:
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 Information:
ICSI Technical Report TR-92-021
Bibliographic Reference:
B. Codenotti and L. Margara. Local Properties of Some NP-Complete Problems. ICSI Technical Report TR-92-021, April 1992
Author: B. Codenotti and L. Margara
Group: ICSI Technical Reports
Date: April 1992
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-92-021.pdf
Overview:
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 Information:
ICSI Technical Report TR-92-021
Bibliographic Reference:
B. Codenotti and L. Margara. Local Properties of Some NP-Complete Problems. ICSI Technical Report TR-92-021, April 1992