Combinatorial and applied graph algorithms (M. Mata-Montero)

Many interesting problems, despite being algorithmically solvable, do not admit feasible practical solutions. The most common obstacle to a practical solution of a recursive problem is the immense amount of computational resources required by the algorithm solving it. Our intent is to identify families of instances for which, otherwise intractable problems, can be solved efficiently.

The theory of graphs offers many optimization problems for which no efficient (polynomial time) solutions are known. In some cases, it is worthwhile to restrict the instances of the problem to finite sets. In this case, a difficulty is that the traditional complexity measures do not apply, so, new ways of measuring the efficiency of algorithms must be devised. In a more conventional way, problems are restricted to infinite families of instances which admit efficient solution according to the conventional complexity measures.

Revised: 2006.1.17