A crucial choice in the definition of local search algorithms for the solution of
combinatorial optimization problems is the choice of the neighborhood structure.
Particularly appealing are those neighborhoods that can be searched efficiently
despite their large size. In the talk we consider the use of exponential size
neighborhoods in three graph problems.

The first problem is the classical graph coloring problem (GCP) whose partitioning
representation lends itself to the definition of a cyclic exchange neighborhood that
can be searched by dynamic programming techniques.  The second problem is the graph
set T-coloring problem (GSTCP) which is a generalization of the GCP where a set of
colors has to be assigned to each vertex. The neighborhood examined considers the
reassignment of all the colors assigned at a vertex and it is searched by means of a
randomized recursive procedure. The third problem is the 2-edge-connectivity
augmentation problem (E1-2AUG) which consists in finding an augmentation to a
minimum spanning tree such that the resulting graph is 2-edge-connected. The
formulation of this problem allows for the use of a shortest path based neighborhood.

All these neighborhood structures can be searched efficiently and have favorable
analytical properties, yet when it comes to experimental tests they do not always
entail an improvement over local search algorithms that use a more simple
neighborhood structure. After a brief description of well-designed experiments, we
report the experimental results for the three cases studied.