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

      0 references
      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
      [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

      Identifiers

      0 references
      0 references
      0 references
      0 references