Given a graph <i>G</i> with <i>n</i> vertices and stability number <img src="alpha.gif" align=bottom>(<i>G</i>), Turán's theorem gives a lower bound on the ...

We study empirically the topology of the local minima of the 3-SAT problem. In particular, we analyze the size of the plateaus, their altitude, their attrac...

Chopping a graph <i>G</i> means removing one edge from each connected component of <i>G</i> in parallel, and repeating this until no edges remain. The requi...

This article considers a tool loading problem whose objective is to minimize the number of tool switches over time in order to process several parts on a fl...

Splitting a tree is defined as removing all edges of a chain and disconnecting one from the other edges incident with that chain. Splitting a forest is simu...

Given a binary matrix <i>E</i>, the Seriation Problem consists of determining a permutation of the rows of <i>E</i> minimizing the sum over all columns of t...

In a first attempt to explain the good behavior of local improvement heuristics (such as Tabu Search and Simulated Annealing) for the <i>k</i>-coloring prob...

We derive from Boolean methods a transformation which, when it can be applied, builds from a graph <i>G =</i> (<i>V,E</i>) a new graph <i>G'=</i> (<i>V',E'<...

For a weighted graph <i>G =</i> (<i>V,E</i>), the maximum weighted <i>k</i>-coloring problem is to color a set of vertices of maximum weight using <i>k</i> ...

We describe two new classes of graphs for which the stability number can be computed in polynomial time. The first approach is based on an iterative procedu...

The purpose of this paper is to describe a new tabu search heuristic for the vehicle routing problem with capacity and route length restrictions. The algori...

A bounded vertex coloring of a graph <i>G</i> is a usual vertex coloring in which each color is used at most <i>k</i> times (where <i>k</i> is a given numbe...

We address in this paper the problem of finding an optimal strategy for dealing with bottleneck machines and bottleneck parts in the cell formation process ...

We describe a new class of graphs for which the stability number can be obtained in polynomial time. The algorithm is based on an iterative procedure which...