No label defined (Q3740231)

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 3974289
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3974289

      Statements

      0 references
      0 references
      0 references
      1985
      0 references
      recursive graph
      0 references
      theory of linear computation
      0 references
      domination number
      0 references
      tree
      0 references
      NP-complete problems
      0 references
      [For the entire collection see Zbl 0583.00003.] The paper is an introduction to the new theory of linear computation which not only explains the linearity of many of the known algorithms, but also predicts the existence of other linear algorithms. The theory is illustrated by applying it to the design of a variant of an existing linear algorithm for calculating the domination number of a tree. Also, the authors present tables indicating 20 families of graphs and 34 NP- complete problems for which this theory predicts that a linear algorithm can be constructed for solving the given problem for any graph in the given family.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references