scientific article; zbMATH DE number 3974289

From MaRDI portal
Publication:3740231





[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.




Cited in
(31)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3740231)