Name
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 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. |
Year | DOI | Venue |
|---|---|---|
1983 | 10.1007/3-540-12896-4_378 | Logic of Programs |
Keywords | Field | DocType |
deriving efficient graph algorithms,depth first search | Program transformation,Search algorithm,Biconnected component,Computer science,Theoretical computer science,Graph bandwidth,Graph (abstract data type),Reverse-delete algorithm,Moral graph,Best-first search | Conference |
Volume | ISSN | ISBN |
164 | 0302-9743 | 3-540-12896-4 |
Citations | PageRank | References |
1 | 0.35 | 15 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| John H. Reif | 1 | 4180 | 810.75 |
| William L. Scherlis | 2 | 340 | 63.64 |