Deriving Efficient Graph Algorithms.
Abstract
Ten years ago Hopcroft and Tarjan discovered a class of very fast algorithms for solving graph problems such as biconnectivity and strong connectivity. While these depth-first-search algorithms are complex and can be difficult to understand, the problems they solve have simple combinatorial definitions that can themselves be considered algorithms, though the might be very inefficient or even infinitary. We demonstrate here how the efficient algorithms can be systematically derived using program transformation steps from the intuitive but preliminary definitions. There are several justifications for this work. First, we believe that the evolutionary approach used in this paper offers more natural explanations of the algorithms than the usual a posteriori proofs that appear in textbooks. Second, the derivations illustrate several high-level principles of program derivation and suggest methods by which these principles can be realized by sequences of program transformation steps. Third, these examples illustrate how external domain-specific knowledge can enter into the program derivation process. This is the first occasion that such efficient graph algorithms have been systematically derived. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1982
- Accession Number
- ADA122828
Entities
People
- John Reif
- William Scherlis
Organizations
- Harvard University