No label defined (Q3707401)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3936509
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3936509 |
Statements
1982
0 references
data structures
0 references
efficiency
0 references
Algebraic transformations of simple iterative algorithms
0 references
strongly connected components of a graph
0 references
0.7577996253967285
0 references
0.7518048882484436
0 references
[For the entire collection see Zbl 0551.00013.] [English version in Lect. Notes Comput. Sci. 122, 430-440 (1981; Zbl 0477.68035).] Algebraic transformations of simple iterative algorithms are quoted. Two interesting examples are given. The first one concerns the computation of strongly connected components of a graph. The method shows how to obtain from a straightforward \(mn^ 2\)-algorithm an efficient max(m,n)- algorithm. Another example shows how to obtain an efficient algorithm for the computation of the minimal relation Q satisfying: \[ P(x_ 1,...,x_ n)\quad \Rightarrow \quad Q(x_ 1,...,x_ n) \] \[ Q(x_ 1,...,x_ n)\quad and\quad R(z_ 1,...,z_ m)\quad \Rightarrow \quad Q(y_ 1,...,y_ n). \] The algebraic method was also used in practice, e.g. the author quotes an example of a PL/1 program of over 2000 statements optimized to a 10 times speed-up.
0 references