Skip to main content
Journal cover image

Deriving efficient graph algorithms (summary)

Publication ,  Conference
Reif, JH; Scherlis, WL
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
January 1, 1984

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 they might be very inefficient or even infinitary. We demonstrate here how the efficient algorithms can be systematically derived using program transformation steps from the initial definitions. This is the first occasion that these efficient graph algorithms have been systematically derived. There are several justifications for this work. First, the derivations illustrate several high-level principles of program derivation and suggest methods by which these principles can be realized as sequences of program transformation steps. Second, 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. Third, these examples illustrate how external domain-specific knowledge can enter into the program derivation process. Finally, we believe that future programming tools will be semantically based and are likely to have their foundations in a logic of program derivation. By working through complex examples such as those presented here, we make steps towards a conceptual and formal basis for these tools.

Duke Scholars

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

ISBN

9783540128960

Publication Date

January 1, 1984

Volume

164 LNCS

Start / End Page

421 / 441

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J. H., & Scherlis, W. L. (1984). Deriving efficient graph algorithms (summary). In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 164 LNCS, pp. 421–441). https://doi.org/10.1007/3-540-12896-4_378
Reif, J. H., and W. L. Scherlis. “Deriving efficient graph algorithms (summary).” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 164 LNCS:421–41, 1984. https://doi.org/10.1007/3-540-12896-4_378.
Reif JH, Scherlis WL. Deriving efficient graph algorithms (summary). In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1984. p. 421–41.
Reif, J. H., and W. L. Scherlis. “Deriving efficient graph algorithms (summary).” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 164 LNCS, 1984, pp. 421–41. Scopus, doi:10.1007/3-540-12896-4_378.
Reif JH, Scherlis WL. Deriving efficient graph algorithms (summary). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1984. p. 421–441.
Journal cover image

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

ISBN

9783540128960

Publication Date

January 1, 1984

Volume

164 LNCS

Start / End Page

421 / 441

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences