Calculating with Relations for Graph Algorithmics.
Jesús N. Ravelo · 1997
Much emphasis has been placed in recent years on deriving or calculating programs rather than proving them correct. Adequate calculational frameworks are needed to support such an approach. The present work explores the use of a calculus of relations to express and reason about graph properties in an algorithmic context. We take a generic program that computes a maximal set, over some universe, satisfying some predicate P and calculate two instances of it: the computation of maximal independent sets of vertices in a graph, and the computation of maximal sets of edges without cycles (i.e. maximal forests).