INDUCTIVE ALGORITHMS ON FINITE TREES

Abstract

Many algorithms for calculating graph theoretic quantities on trees rely implicitly on an inductive procedure for calculating a certain function defined on the vertices of the tree, after which the function is used to determine the quantity. Examples of such quantities are the diameter, 1-centre, core and cutting centre. Each of the latter can be calculated in linear time, but in the last three cases this is far from obvious, and they have been the subjects of research papers in recent years.