A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem
The problem is to find a spanning tree with maximal number of internal vertices in an undirected graph. It seems to have already earlier attracted some activity. Here, a 7-line verbally formulated algorithm is presented. It is based on a sequence of ideas to reduce the given graph. Performance ratios of \(\frac{4}{3}\) vs. \(\frac{3}{2}\) and others in the literature are discussed.
scientific article; zbMATH DE number 7319300