Deriving General Schemes for Classes of Graph Algorithms

Existing approaches to formal developments of graph algorithms mostly use calculi which are suitable only up to a certain stage or provide derivations of single graph algorithms only. In the present book, contrastively, the step to elegant formal derivations of algorithm schemes for entire classes of graph algorithms is taken. Based on an algebra of formal languages a framework suitable for a uniform treatment of entire classes of graph algorithms is introduced. It enables us to define general operations for classes of graph problems. The particular classes we deal with are layer-oriented graph traversal problems and algorithms treating hamiltonian paths. It turns out that a surprising variety of problems is covered by these two classes.