ABSTRACT
Graphs are among the most fundamental mathematical models in computer science and many practical problems in routing, scheduling, and other areas have natural graph theoretical formalizations. It has, however, long been realized that a large class of important algorithmic problems seems to evade all attempts of efficient solvability, leading to the theory of NP-hardness as model for computational intractability.
