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
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
0.779649019241333
0 references
0.7560250163078308
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