zbMATH — the first resource for mathematics

A methodology for constructing linear graph algorithms. (English) Zbl 0603.68040
Proc. Conf., Sundance/Utah 1985, Congr. Numerantium 50, 43-60 (1985).
[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.
Reviewer: L.Olaru

68Q25 Analysis of algorithms and problem complexity
05C99 Graph theory
68R10 Graph theory (including graph drawing) in computer science
05C05 Trees
05C35 Extremal problems in graph theory